Car Pooling (M)
題目
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:
Input: trips = [[2,1,5],[3,3,7]], capacity = 4
Output: false
Example 2:
Input: trips = [[2,1,5],[3,3,7]], capacity = 5
Output: true
Example 3:
Input: trips = [[2,1,5],[3,5,7]], capacity = 3
Output: true
Example 4:
Input: trips = [[3,2,7],[3,7,9],[8,3,9]], capacity = 11
Output: true
Constraints:
trips.length <= 1000trips[i].length == 31 <= trips[i][0] <= 1000 <= trips[i][1] < trips[i][2] <= 10001 <= capacity <= 100000
題意
一輛有容量限制的公交車一路向東，在每個里程點會有若干乘客上車或下車，問能否運輸所有乘客，
思路
求出每個里程點的人員變動數量，在經過這些歷程點時車上人數進行相應變化，如果某一點車上人數超出限制，說明無法運輸所有乘客，
代碼實作
Java
class Solution {
public boolean carPooling(int[][] trips, int capacity) {
int[] change = new int[1001];
for (int[] trip : trips) {
change[trip[1]] += trip[0];
change[trip[2]] -= trip[0];
}
int remain = 0;
for (int value : change) {
remain += value;
if (remain > capacity) {
return false;
}
}
return true;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/101268.html
標籤：其他
上一篇：關于IS-IS在P2P網路下，CSNP只發送一次，但是CSNP報文只發送一次，若第一個CSNP或者對端路由器發回來的第一個PSNP丟失，那怎么辦？