Skip to content

1094. Car Pooling 👍

  • Time: $O(n\log n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
 public:
  bool carPooling(vector<vector<int>>& trips, int capacity) {
    int currentPassengers = 0;
    map<int, int> timeline;

    for (const vector<int>& trip : trips) {
      const int nPassengers = trip[0];
      const int start = trip[1];
      const int end = trip[2];
      timeline[start] += nPassengers;
      timeline[end] -= nPassengers;
    }

    for (const auto [_, passengerChange] : timeline) {
      currentPassengers += passengerChange;
      if (currentPassengers > capacity)
        return false;
    }

    return true;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
  public boolean carPooling(int[][] trips, int capacity) {
    int currentPassengers = 0;
    Map<Integer, Integer> timeline = new TreeMap<>();

    for (int[] trip : trips) {
      final int nPassengers = trip[0];
      final int start = trip[1];
      final int end = trip[2];
      timeline.merge(start, nPassengers, Integer::sum);
      timeline.merge(end, -nPassengers, Integer::sum);
    }

    for (final int passengerChange : timeline.values()) {
      currentPassengers += passengerChange;
      if (currentPassengers > capacity)
        return false;
    }

    return true;
  }
}