class Solution {
    public int findContentChildren(int[] g, int[] s) {
        //sort both the greed 'g' and size 's' array in ascending order
        //if the greed 'i'th is less than or equal to the 'j'th size then it can be satisfied else no greed (k, where k>i)  will be satisfied with the current size 'j' ( since the greeds are sorted in ascending order)
        //and we have to move to the next size 'j+1' to check the same
        Arrays.sort(g);
        Arrays.sort(s);
        int count =0;
        int i= 0,j = 0;
        while(i<g.length && j<s.length){
            if(g[i]<=s[j]){
                count++;
                i++;
                j++;
            }
            else{
                j++;
            }
        }
        return count;
    }
}

class Solution {
    public boolean lemonadeChange(int[] bills) {
        int five = 0;
        int ten  =0;
        int twenty = 0;
        for(int i = 0;i<bills.length;i++){
            if(bills[i] == 5) five++;
            else if(bills[i] ==10 && five>0){
                five--;
                ten++;
            }
            else if(bills[i] == 20 && ten>0 && five>0){
                twenty++;
                ten--;
                five--;
            }
            else if(bills[i] ==20 && five>2){
                five = five-3;
            }
            else return false;
        }
        return true;
    }
}

class Solution {
    static int solve(int bt[] ) {
        //shorted job first
        Arrays.sort(bt);
        //example : 
        /*
        n = 5
        bt = [4,3,7,1,2]
        after sorting : bt[] = [1,2,3,4,7] = [p4,p5,p2,p1,p3]

        p4      p5      p2      p1              p3
        0---1------3--------6----------10-------------------17
        waiting time for p4 : 0,  p5 :1, p2: 3,p1: 6, p3 : 10
        total average waiting time : 20/5 = 4

        */
        int time = 0;
        int wt = 0;

        for(int i =0;i<bt.length-1;i++){
            time+=bt[i];
            wt+=time;
        }

        return wt/bt.length;
  }
}

class Solution {
    static int canReach(int[] A, int N) {
        //observations: if the array does not have 0, in that case we can alwys reach to last index
        //because we can always keep on jumpting till we reach the last index)
        /*
        Undersatnding with example : 
        N = 6
        A[] = {1, 2, 0, 3, 0, 0} 
        let maxIndex = 0;
        at index 0 max jump possible is 0+1 = 1 ( index+value = next index that can be raeched), making maxIndex = 1
        at index 1 maxjump possible is 1+2 = 3, making maxIndex = 3
        at index 2 maxjump possible is 0+0 = 0, maxIndex remains same
        at index 3 maxjump possible is 3+3 = 6, maxIndex = 6 > N-1, hence possible to reach the last index 
        */
        int maxIndex = 0;
        for(int i  = 0;i<N;i++){
            if(i > maxIndex) return 0;
            maxIndex = Math.max(maxIndex,i+ A[i]);
            if(maxIndex >=N-1) return 1;// early exit
        }
        return 1;
    }
}

//dp approach:
class Solution {
    public int jump(int[] nums) {
        int dp[] = new int[nums.length];
        Arrays.fill(dp,-1);
        return min(0,nums,dp);
    }
    public int min(int index ,int nums[], int dp[]){
        if(index >= nums.length-1) return 0;
        if(dp[index]!=-1) return dp[index];

        int min  = 10001;
        for(int jump  =1;jump<=nums[index];jump++){
            min  =Integer.min(min, 1 + min(index+jump, nums,dp));
        }
        return dp[index] = min;
    }
}

/*
TC: O(n), outer loop is just for checking if r<n-1, inner loop is doing the
traversal for n elements
This is greedy because in every iteration we are trying to find out the farthest index that we can jump to.
example :
nums = [2,3,1,1,4]

for the index 0 , we can jump to index 1 or we can jump to index 2
So range for the first jump (jump = 1) becomes index: 1,2
from index 1 we can jump to index 2,3,4 ( if we jump to index 2 jump = 2, if we jump to index 3 jump = 2 and if we jump to index 4 
jump =2, so we want to minimize the countOfJump and maximize the range of jump which is index 4 in this case)
We can have left and right pointer intialized with 0, then we can iterate left till right to find the max index that can be reached, then 
update left and right to point to new range
Do it till the n-1 index is reached
*/

class Solution {
    public int jump(int[] nums) {
        int left =0,right =0;
        int jump = 0;
        while(right<nums.length-1){
            int farthest = 0;
            for(int i =left;i<=right;i++){
                farthest = Integer.max(farthest, i+ nums[i]);
            }
            //now update left and right to point to new range
            left = right+1;
            right  =farthest;

            jump++;
        }
        return jump;
    }
}

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
{
    public static int activitySelection(int start[], int end[], int n)
    {
        // add your code here
        PriorityQueue<Activity> q = new PriorityQueue<>((a,b)-> a.end-b.end); //acitivites are sorted on the basis of end time
        for(int  i =0;i<n;i++){
            q.add(new Activity(start[i],end[i]));
        }

        int count = 0;
        int previousEndTime = -1;// previousEndTime initialized with -1;
        while(!q.isEmpty()){
            Activity a = q.remove();
            //an activity can only be done if the it's start time is greater than the end time of previuos activity
            if(previousEndTime < a.start){
                count++;
                previousEndTime = a.end;
            }
        }
        return count;
    }
}
class Activity{
    int start;
    int end;
    public Activity(int s, int e){
        start = s;
        end = e;
    }
}

//we can directly sort the intervals array and iterate over it, //instead of using Queue.
class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        //same as N meetings/no. of activities
        //sort the intervals based on end time of each pair
        Queue<Pair<Integer,Integer>> q = new PriorityQueue<>((a,b)->a.getValue()-b.getValue());
        for(int i  = 0;i<intervals.length;i++){
            q.add(new Pair(intervals[i][0], intervals[i][1]));
        }
        int previousEndTime = Integer.MIN_VALUE;
        int count = 0;
        while(!q.isEmpty()){
            Pair<Integer,Integer> p  = q.remove();
            int start = p.getKey();
            int end = p.getValue();
            if(start>=previousEndTime){
                count++;
                previousEndTime = end;
            }
        }
        return intervals.length-count;

    }
}

class Solution {
    public int findMinArrowShots(int[][] points) {
        // this is same as non-overlapping intervals/n meetings in a room/maximum activities problem
        //sort the given array based on increasing xend co-ordinates and find out all the non-overlapping interval
        Arrays.sort(points,(a,b)->Integer.compare(a[1],b[1]));

        long previousEnd = Long.MIN_VALUE;
        int count  =0;
        for(int i =0;i<points.length;i++){
            // check if the Xstart of current baloon is greater than the previous ballon's Xend
            if(previousEnd < points[i][0]){
                count++;
                previousEnd = points[i][1];
            }
        }
        return count;
    }
}

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int start = newInterval[0], end = newInterval[1];
        if(intervals.length==0) return new int[][]{{start,end}};

        List<Pair<Integer,Integer>> list = new ArrayList<>();
        int  i=0;
        while(i  < intervals.length){
            if(intervals[i][1] < start){ // if the start time of newInterval is greater than the end time of current array, they are not overlapping
                list.add(new Pair(intervals[i][0],intervals[i][1]));
            }
            else{ // overlapping intervals
                start = Integer.min(start, intervals[i][0]); //start will be the min of both intervals[i][0] or newIntervals[0]
                //now finding the end time 
                while(i< intervals.length && end >= intervals[i][0]  ){ //as long as end time is overlapping with start time of next intervals keep going ahead
                    end = Integer.max(end, intervals[i][1]);//since the start time of next intervals is overlapping with the 'end', it will be udpated as end = Integer.max(end, intervals[i][1])
                    //i.e final end time will be the max end time between the 'end' and intervals[i][1]
                    i++;
                }
                //finally we have new (start, end);
                list.add(new Pair(start,end));

                // if still some intervals are remaining in the intervals array add them in the list as well
                while(i< intervals.length){
                    list.add(new Pair(intervals[i][0],intervals[i][1]));
                    i++;
                }
            }
            i++;
        }
        // edge case what if the newIntervals are not overlapping at all, then they will satisfy the below condition
        //newIntervals start time will be greater than the end time of last intervals[i][1]
        if(start > intervals[intervals.length-1][1]) list.add(new Pair(start,end));
        return getArray(list);
    }
    public int[][] getArray(List<Pair<Integer,Integer>> list){
        int arr[][] = new int[list.size()][2];
        int index = 0;
        for(Pair<Integer,Integer> p  : list){
            arr[index][0] = p.getKey();
            arr[index++][1] = p.getValue();
        }
        return arr;
    }
}

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> list = new ArrayList<>();
        int i = 0,n = intervals.length;
        //left part
        while(i<n && intervals[i][1] < newInterval[0]){
            list.add(intervals[i]);
            i++;
        }
        //overlapping part
        while(i<n && intervals[i][0] <= newInterval[1]){
            newInterval[0] = Integer.min(newInterval[0],intervals[i][0]);
            newInterval[1] = Integer.max(newInterval[1],intervals[i][1]);
            i++;
        }
        list.add(newInterval);
        //right part
        while(i<n){
            list.add(intervals[i]);
            i++;
        }
        int result[][] = new int[list.size()][2];
        for(i=0;i<list.size();i++){
            result[i] = list.get(i);
        }
        return result;
    }
}

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        //sort them on the basis of before, overlappingintervals and  after 

        List<int []> before = new ArrayList<>();
        List<int[]> after = new ArrayList<>();

        for (int [] a : intervals){
            if(a[1] < newInterval[0]) before.add(a);
            else if (newInterval[1] < a[0]) after.add(a);
            else{
                newInterval[0] = Math.min(newInterval[0],a[0]);
                newInterval[1] = Math.max(newInterval[1],a[1]);
            }
        }
        int result [][]= new int[before.size()+1 + after.size()][2];
        int index  =0;
        for(int i =0;i< before.size();i++){
            result[index] = before.get(i);
            index++; 
        }

        result[index++] = newInterval;
         for(int i =0;i< after.size();i++){
            result[index] = after.get(i);
            index++; 
        }  
        return result;
    }
}

class Solution
{
   //greedy approach:Sort jobs based on the profit in descending order and try to perform jobs as close to their deadline as possible 
   ///if the a job with deadline x can not be performed on day x try to perform it on day x-1, else x-2,...0

    int[] JobScheduling(Job arr[], int n)
    {
        Arrays.sort(arr,(a,b)->b.profit-a.profit);
        int maxDeadline = -1;
        for(Job job : arr){
            maxDeadline = Integer.max(maxDeadline, job.deadline);
        }
        int slots[] = new int[maxDeadline];//max no. of days available
        int noOfjobs =0;
        int maxProfit= 0;
        Arrays.fill(slots,-1);
        for(int i =0;i<arr.length;i++){
            for(int j  = arr[i].deadline-1;j>=0;j--){//try execute the job as close to its deadline as possible
                if(slots[j]==-1){// if the day is available 
                    noOfjobs++;
                    maxProfit+=arr[i].profit;// get the profit of the ith job
                    slots[j] = arr[i].id;// get the id of the ith job and put in jth slot/day
                    break;// since the job has been allocated exit now 
                }
            }
        }
        return new int[]{noOfjobs,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 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[]) {
        // add your code here
        Queue<Integer> q = new PriorityQueue<>();
        q.add(-1);// lets assume a train will depart at -1 from ( as we need atleat 1 platform)
        Queue<Train> queue = new PriorityQueue<>((a,b)-> a.a-b.a);
        for(int i =0;i<arr.length;i++){
            queue.add(new Train(arr[i], dep[i]));
        }
        while(!queue.isEmpty()){
            Train t = queue.remove();
            // if the arrival time of next train is greater the departure time of the train that is going to leave the station first (before any other train on the platform)
            if(t.a > q.peek()) q.remove(); // same platform can be utilized 
            q.add(t.d); // or another platform will be needed
        }
        return q.size();// no. of plaform

    }
}
class Train{
    int a;
    int d;
    public Train(int a, int d){
        this.a  =a;
        this.d = d;
    }
}

/*
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) {
        Queue<Item> q = new PriorityQueue<>((a,b)-> Double.compare((double)b.value/(double)b.weight,(double)a.value/(double)a.weight));
        for(int i =0;i<arr.length;i++){
            q.add(arr[i]);
        }
        double profit = 0.0;
        while(!q.isEmpty()){
            Item i = q.remove();
            if(w>=i.weight){
                w = w-i.weight;
                profit+=i.value;
            }
            else{
                profit+= (double)(((double)i.value/(double)i.weight)*(w));
                w = 0;// or break;
            }
        }
        return profit;
    }
}

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);
    }
}