[LeetCode] 1094. Car Pooling

 Problem : https://leetcode.com/problems/car-pooling/

This problem is similar to the meeting room problems.

Use priority queue to process the timestamp when the 'occupied' counter be updated.

When 2 trips start on the same timestamp, it's important to decrease the 'occupied' counter first before increasing the 'occupied' counter.

Time complexity = O ( N * Log N ), N = length of the trips.

class Solution {
    public boolean carPooling(int[][] trips, int capacity) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
        
        for ( int i=0; i < trips.length; i++) {
            // increase counter when the trip starts
            pq.offer(new int[]{trips[i][1], trips[i][0]});
            // decrease counter when the trip ends
            pq.offer(new int[]{trips[i][2], -1*trips[i][0]});
        }
        
        int occupied = 0;
        
        while (!pq.isEmpty() && occupied <= capacity) {
            occupied += pq.poll()[1];
        }
        
        return occupied <= capacity;
    }
}