1094. Car Pooling.md

Solution

• pq min heap
• similar idea from meeting room 2 and add while loop to pop out the element in the pq
• time O(nlg(n)) ?

class Solution {
    class Entry{
        public int ending;
        public int num;
        public Entry(int ending, int num){
            this.ending = ending;
            this.num = num;
        }
    }
    public boolean carPooling(int[][] trips, int capacity) {
        //using min heap
        if(trips.length==0) return true;
        PriorityQueue<Entry> pq = new PriorityQueue<Entry>((Entry a, Entry b)->a.ending-b.ending);
        Arrays.sort(trips, (a,b)->a[1]-b[1]);
        pq.add(new Entry(trips[0][2], trips[0][0]));
        int sum = trips[0][0];
        for(int i = 1; i<trips.length; i++){
            //pay attention to while !!!!!!!
            while(!pq.isEmpty() && trips[i][1]>=pq.peek().ending){
                Entry entry = pq.poll();
                sum-=entry.num;
            }
            sum+=trips[i][0];
            
            if(sum> capacity) return false;
            pq.add(new Entry(trips[i][2], trips[i][0]));
        }
        
        return true;
    }
}

Solution 2

• https://leetcode.com/problems/car-pooling/discuss/501530/Java-easy-to-understand-solution-with-explanation