差分数组-leetcode1094
2023-04-12
车上最初有capacity个空座位。车只能向一个方向行驶（也就是说，不允许掉头或改变方向）
给定整数capacity和一个数组trips,trip[i] = [numPassengersi, fromi, toi]表示第i次旅行有numPassengersi乘客，接他们和放他们的位置分别是fromi和toi。这些位置是从汽车的初始位置向东的公里数。
当且仅当你可以在所有给定的行程中接送所有乘客时，返回true，否则请返回false。
示例 1：
输入：trips = [[2,1,5],[3,3,7]], capacity = 4
输出：false示例 2：
输入：trips = [[2,1,5],[3,3,7]], capacity = 5
输出：true提示：
1 <= trips.length <= 1000trips[i].length == 31 <= numPassengersi <= 1000 <= fromi < toi <= 10001 <= capacity <= 105
思路：差分数组，对于区间频繁修改的数组
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public boolean carPooling(int[][] trips, int capacity) {
int n = 1000;
int[] result = new int[n];
for (int[] trip : trips) {
int numPassengersi = trip[0];
if (numPassengersi > capacity) {
return false;
}
int start = trip[1] - 1;
int end = trip[2] - 1 - 1;
result[start] += numPassengersi;
if (end + 1 < n) {
result[end + 1] -= numPassengersi;
}
}
for (int i = 0; i < 10; i++) {
System.out.print(result[i] + " ");
}
System.out.println();
for (int i = 1; i < n; i++) {
result[i] += result[i - 1];
}
for (int i = 0; i < 10; i++) {
System.out.print(result[i] + " ");
}
System.out.println();
for (int i = 1; i < n; i++) {
if (result[i] > capacity) {
System.out.println(result[i] + " " + capacity);
return false;
}
}
return true;
}
}
//leetcode submit region end(Prohibit modification and deletion)
本文仅代表作者观点，版权归原创者所有，如需转载请在文中注明来源及作者名字。
免责声明：本文系转载编辑文章，仅作分享之用。如分享内容、图片侵犯到您的版权或非授权发布，请及时与我们联系进行审核处理或删除，您可以发送材料至邮箱：service@tojoy.com