package leetcode;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * https://leetcode.com/problems/car-pooling/
 */
public class Problem1094 {
    public boolean carPooling(int[][] trips, int capacity) {
        Arrays.sort(trips, (a, b) -> {
            int cmp = Integer.compare(a[1], b[1]);
            if (cmp == 0) {
                return Integer.compare(a[2], b[2]);
            }
            return cmp;
        });
        int cap = capacity;
        PriorityQueue<NumPassengersEndLocation> queue = new PriorityQueue<>(
            Comparator.comparingInt(a -> a.endLocation));
        for (int i = 0; i < trips.length; i++) {
            int numPassengers = trips[i][0];
            int startLocation = trips[i][1];
            int endLocation = trips[i][2];
            if (!queue.isEmpty() && queue.peek().endLocation <= startLocation) {
                cap += queue.remove().numPassengers;
            }
            cap -= numPassengers;
            if (cap < 0) {
                return false;
            }
            queue.add(new NumPassengersEndLocation(numPassengers, endLocation));
        }
        return true;
    }

    private static class NumPassengersEndLocation {
        private final int numPassengers;
        private final int endLocation;

        public NumPassengersEndLocation(int numPassengers, int endLocation) {
            this.numPassengers = numPassengers;
            this.endLocation = endLocation;
        }
    }

    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
        System.out.println(prob.carPooling(new int[][]{{3, 2, 8}, {4, 4, 6}, {10, 8, 9}}, 11)); // true
    }
}

@@ -16,62 +16,8 @@
 e;%0A%0A
-import java.util.Arrays;%0Aimport java.util.Comparator;%0A
 impo
@@ -199,27 +199,56 @@
     
-Arrays.sort(trips, 
+PriorityQueue%3CTrip%3E queue = new PriorityQueue%3C%3E(
 (a, 
@@ -281,35 +281,31 @@
 p = 
-Integer.compare(a%5B1%5D, b%5B1%5D)
+a.location - b.location
 ;%0A  
@@ -350,402 +350,305 @@
     
-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
+// End location should come first.%0A                return Integer.compare(b.passengers, a.passengers);%0A            %7D%0A            return cmp;%0A        %7D);%0A        for (int%5B%5D trip : trips) %7B%0A            queue.add(new Trip(-trip%5B0%5D, trip%5B1%5D));%0A            queue.add(new Trip(trip%5B0%5D, trip%5B2%5D))
 ;%0A      
     
@@ -647,43 +647,38 @@
     
+  %7D%0A
       
+  
 int 
-endLocation = trips%5Bi%5D%5B2%5D
+cap = capacity
 ;%0A  
@@ -683,22 +683,21 @@
         
-    if
+while
  (!queue
@@ -710,309 +710,126 @@
 ty()
- && 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));
+) %7B%0A            cap += queue.poll().passengers;%0A            if (cap %3C 0) %7B%0A                return false;%0A            %7D
 %0A   
@@ -892,32 +892,12 @@
 ass 
-NumPassengersEndLocation
+Trip
  %7B%0A 
@@ -917,28 +917,25 @@
 e final int 
-numP
+p
 assengers;%0A 
@@ -955,28 +955,25 @@
 e final int 
-endL
+l
 ocation;%0A%0A  
@@ -989,41 +989,18 @@
 lic 
-NumPassengersEndLocation
+Trip
 (int 
-numP
+p
 asse
@@ -1010,20 +1010,17 @@
 rs, int 
-endL
+l
 ocation)
@@ -1039,20 +1039,17 @@
    this.
-numP
+p
 assenger
@@ -1056,12 +1056,9 @@
 s = 
-numP
+p
 asse
@@ -1081,20 +1081,17 @@
    this.
-endL
+l
 ocation 
@@ -1096,617 +1096,27 @@
 n = 
-endLocation;%0A        %7D%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem1094 prob = new Problem1094();%0A//        System.out.println(prob.carPooling(new int%5B%5D%5B%5D%7B%7B2, 1, 5%7D, %7B3, 3, 7%7D%7D, 4)); // false%0A//        System.out.println(prob.carPooling(new int%5B%5D%5B%5D%7B%7B2, 1, 5%7D, %7B3, 3, 7%7D%7D, 5)); // true%0A//        System.out.println(prob.carPooling(new int%5B%5D%5B%5D%7B%7B2, 1, 5%7D, %7B3, 5, 7%7D%7D, 3)); // true%0A//        System.out.println(prob.carPooling(new int%5B%5D%5B%5D%7B%7B3, 2, 7%7D, %7B3, 7, 9%7D, %7B8, 3, 9%7D%7D, 11)); // 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
+location;%0A        %7D
 %0A   

Solve problem 1094