Skip to content

1094. Car Pooling 👍

Approach 1: Line Sweep

  • 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> line;

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

    for (const auto [_, passengerChange] : line) {
      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> line = new TreeMap<>();

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

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

    return true;
  }
}

Approach 2: Bucket

  • Time: $O(\max(n, 1001))$
  • Space: $O(1001) = O(1)$
 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;
    vector<int> line(1001);

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

    for (const int passengerChange : line) {
      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;
    int[] line = new int[1001];

    for (int[] trip : trips) {
      final int nPassengers = trip[0];
      final int start = trip[1];
      final int end = trip[2];
      line[start] += nPassengers;
      line[end] -= nPassengers;
    }

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

    return true;
  }
}