class Solution 
{
    //Function to find the maximum number of meetings that can
    //be performed in a meeting room.
    public static int maxMeetings(int start[], int end[], int n)
    {
        // add your code here
        PriorityQueue<MData> q  = new PriorityQueue<>((a,b)-> a.getEnd()-b.getEnd());
        for(int i =0;i<start.length;i++){
            q.add(new MData(start[i],end[i],i));
        }
        int count =0;
        int ps  = -1,pe = -1;
        while(!q.isEmpty()){
            MData m = q.remove();
            if(m.getStart() > pe){
                count ++;
                ps = m.getStart();
                pe = m.getEnd();
            }
        }
        return count;
    } 


}
class MData{
        int start;
        int end;
        int index;
        public MData(int s,int e,int i){
            this.start = s;
            this.end = e;
            this.index =i;
        }
        public int getEnd(){
            return this.end;
        }
        public int getStart(){
            return this.start;
        }
        public int getIndex(){
            return this.index;
        }
    }

class Solution
{
    //Function to find the maximum profit and the number of jobs done.
    int[] JobScheduling(Job arr[], int n)
    {
        // Your code here


        int maxDeadline = 0;
        for(int i =0;i<arr.length;i++){
            maxDeadline  = Integer.max(maxDeadline, arr[i].deadline);
        }
         int slots[]  = new int[maxDeadline];
         HashSet<Integer> set = new HashSet<>();
         int result[] = new int[2];
        Arrays.fill(slots,-1);//none of the slots are occupied 

        Arrays.sort(arr,new Comparator<Job>(){
            public int compare(Job a, Job b){
                return b.profit-a.profit;
            }
        });
        // for(int i =0;i<arr.length;i++)
        //     System.out.println(arr[i].deadline);
        int maxJobs = 0;
        int maxProfit =0;
        for(int i =0;i<arr.length;i++){
            int j = arr[i].deadline-1;// we will try to put the job at its deadline
            // if that slot is already occupied by some other jobId then we will decrement
            // the index to see if the ith job can be placed on earlier slots or not
            while(j>=0 && slots[j] !=-1){
                j--;
            }
            //now while loop has exited it can mean only two things
            //either we have found a slot(with index>=0) whose value is -1 (meaning ith job can be place here)
            //or we all the index of the slots from jth to 0th are occupied by other job ids hence
            //we won't be considering this job as it can't be scheduled
            if(j>=0){
                maxProfit+=arr[i].profit;
                maxJobs++;
                slots[j] = arr[i].id; // jth slot is occupied by ith job
            }
        }
        return new int[]{maxJobs,maxProfit};
    }
}

/*
class Job {
    int id, profit, deadline;
    Job(int x, int y, int z){
        this.id = x;
        this.deadline = y;
        this.profit = z; 
    }
}
*/

//User function Template for Java

class Solution
{
    //Function to find the minimum number of platforms required at the
    //railway station such that no train waits.
    static int findPlatform(int arr[], int dep[], int n)
    {
        // add your code here
        Arrays.sort(arr);
        Arrays.sort(dep);
        int i =0,j=0;
        int result = 0;
        int currentPlat =0;
        while(i<arr.length && j< dep.length){
            if(arr[i]<=dep[j]){
                i++;
                currentPlat++;
            }
            else if(arr[i] > dep[j]){
                j++;
                currentPlat--;
            }
            result = Integer.max(result,currentPlat);
        }
        return result;

    }

} 

/*
class Item {
    int value, weight;
    Item(int x, int y){
        this.value = x;
        this.weight = y;
    }
}
*/

class Solution
{
    //Function to get the maximum total value in the knapsack.
    double fractionalKnapsack(int W, Item arr[], int n) 
    {
         Arrays.sort(arr,new Comparator<Item>(){
             public int compare(Item a, Item b){
                 double aa  =(double)a.value/(double)a.weight;
                 double bb = (double)b.value/(double)b.weight;
                 return aa > bb ? -1 : 1;
             }
         });
         double result  =0.0;
         int currentW = 0;
         for(Item i : arr){
             if(W>=i.weight+currentW){
                 currentW+=i.weight;
                 result+= i.value;
             }
             else{
                 int remain = W-currentW;
                 result+= ((double)i.value / (double)i.weight) * (double)remain;
                 break;
             }
         }
         return result;
    }
}

class Solution{

    public int minCoins(int coins[], int M, int V) 
    { 
        // Your code goes here
        int dp[][] = new int[M][V+1];
        for(int row[] : dp) Arrays.fill(row,-1);
        int result  = getCoins(M-1,coins,V,dp);
        return  result==1000000 ? -1 : result ;
    } 
    public int getCoins(int index,int[] coins,int target,int dp[][]){

        if(index==0){
            if(target % coins[index]== 0) return target/coins[index];
            return 1000000;
        }
        if(dp[index][target]!=-1) return dp[index][target];

        int take  = 1000000;
        if(coins[index]<=target){
            take = 1 + getCoins(index,coins,target-coins[index],dp);
        }
        int dontTake = 0 + getCoins(index-1,coins,target,dp);
        return dp[index][target]  = Integer.min(take,dontTake);
    }
}