leetcode 1094

问题

You are driving a vehicle that has capacity empty seats initially available for passengers. The vehicle only drives east (ie. it cannot turn around and drive west.)

Given a list of trips, trip[i] = [num_passengers, start_location, end_location] contains information about the i-th trip: the number of passengers that must be picked up, and the locations to pick them up and drop them off. The locations are given as the number of kilometers due east from your vehicle’s initial location.

Return true if and only if it is possible to pick up and drop off all passengers for all the given trips.

Example 1:

1
2
Input: trips = [[2,1,5],[3,3,7]], capacity = 4
Output: false

Example 2:

1
2
Input: trips = [[2,1,5],[3,3,7]], capacity = 5
Output: true

Example 3:

1
2
Input: trips = [[2,1,5],[3,5,7]], capacity = 3
Output: true

Example 4:

1
2
Input: trips = [[3,2,7],[3,7,9],[8,3,9]], capacity = 11
Output: true

Constraints:

  1. trips.length <= 1000
  2. trips[i].length == 3
  3. 1 <= trips[i][0] <= 100
  4. 0 <= trips[i][1] < trips[i][2] <= 1000
  5. 1 <= capacity <= 100000

分析

思路1: 重新组合 trips，每一个vector\ trips 重新组合成 {start_location, num_passengers} 和 {end_location, -num_passengers}，并按照第一维从小到大的顺序进行排序，第一维相同时，按照第二位从小到大的顺序排序。（主要是先负数然后再整数，“先下后上”）。然后对新的数组求前缀和，在求得过程中若出现前缀和大于capacity的情况，那么返回false，否则返回true。由于排序，时间复杂度 $O(nlogn)$。

思路2: 优化，由于题目中的站点最多有1000个，因此可以统计经过每个站点后车上的人员变化数，然后对其求前缀和，同样在求得过程中若出现前缀和大于capacity的情况，那么返回false，否则返回true。没有排序，时间复杂度 $O(n)$。

代码1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// O(nlogn)
class Solution {
public:
    bool carPooling(vector<vector<int>>& trips, int capacity) {
        vector<vector<int>> t;
        for (vector<int> &trip: trips) {
            t.push_back({trip[1], trip[0]});
            t.push_back({trip[2], -trip[0]});
        }
        sort(t.begin(), t.end());
        
        int sum = 0;
        for (int i = 0; i < t.size(); ++i) {
            sum += t[i][1];
            if (sum > capacity)
                return false;
        }
        return true;
    }
};

代码2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// O(n)
class Solution {
public:
    bool carPooling(vector<vector<int>>& trips, int capacity) {
        vector<int> points(1001, 0);
        for (vector<int> &t: trips) {
            points[t[1]] += t[0];
            points[t[2]] -= t[0];
        }
        int sum = 0;
        for (int p: points) {
            if ((sum += p) > capacity)
                return false;
        }
        return true;
    }
};