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/106370.html
標籤：其他
上一篇：應屆大學生，在醫藥零售公司做MOM開發人員，請問這個職業怎么發展的？本人對技術感興趣想往技術方向走是否要轉崗啊？