package leetcode;

/**
 * https://leetcode.com/problems/car-pooling/
 */
public class Problem1094 {
    public boolean carPooling(int[][] trips, int capacity) {
        // TODO
        return false;
    }

    public static void main(String[] args) {
        Problem1094 prob = new Problem1094();
        System.out.println(prob.carPooling(new int[][]{{2, 1, 5}, {3, 3, 7}}, 4)); // false
        System.out.println(prob.carPooling(new int[][]{{2, 1, 5}, {3, 3, 7}}, 5)); // true
        System.out.println(prob.carPooling(new int[][]{{2, 1, 5}, {3, 5, 7}}, 3)); // true
        System.out.println(prob.carPooling(new int[][]{{3, 2, 7}, {3, 7, 9}, {8, 3, 9}}, 11)); // true
    }
}

@@ -12,16 +12,103 @@
 tcode;%0A%0A
+import java.util.Arrays;%0Aimport java.util.Comparator;%0Aimport java.util.PriorityQueue;%0A%0A
 /**%0A * h
@@ -253,37 +253,1249 @@
     
-// TODO%0A        return false;
+Arrays.sort(trips, (a, b) -%3E %7B%0A            int cmp = Integer.compare(a%5B1%5D, b%5B1%5D);%0A            if (cmp == 0) %7B%0A                return Integer.compare(a%5B2%5D, b%5B2%5D);%0A            %7D%0A            return cmp;%0A        %7D);%0A        int cap = capacity;%0A        PriorityQueue%3CNumPassengersEndLocation%3E queue = new PriorityQueue%3C%3E(%0A            Comparator.comparingInt(a -%3E a.endLocation));%0A        for (int i = 0; i %3C trips.length; i++) %7B%0A            int numPassengers = trips%5Bi%5D%5B0%5D;%0A            int startLocation = trips%5Bi%5D%5B1%5D;%0A            int endLocation = trips%5Bi%5D%5B2%5D;%0A            if (!queue.isEmpty() && queue.peek().endLocation %3C= startLocation) %7B%0A                cap += queue.remove().numPassengers;%0A            %7D%0A            cap -= numPassengers;%0A            if (cap %3C 0) %7B%0A                return false;%0A            %7D%0A            queue.add(new NumPassengersEndLocation(numPassengers, endLocation));%0A        %7D%0A        return true;%0A    %7D%0A%0A    private static class NumPassengersEndLocation %7B%0A        private final int numPassengers;%0A        private final int endLocation;%0A%0A        public NumPassengersEndLocation(int numPassengers, int endLocation) %7B%0A            this.numPassengers = numPassengers;%0A            this.endLocation = endLocation;%0A        %7D
 %0A   
@@ -1589,16 +1589,18 @@
 1094();%0A
+//
         
@@ -1683,16 +1683,18 @@
 / false%0A
+//
         
@@ -1768,32 +1768,34 @@
 %7D, 5)); // true%0A
+//
         System.o
@@ -1865,24 +1865,26 @@
 )); // true%0A
+//
         Syst
@@ -1974,16 +1974,120 @@
 // true%0A
+        System.out.println(prob.carPooling(new int%5B%5D%5B%5D%7B%7B3, 2, 8%7D, %7B4, 4, 6%7D, %7B10, 8, 9%7D%7D, 11)); // true%0A
     %7D%0A%7D%0A

Update problem 1094