LeetCode 1094. Car Pooling
原题链接在这里:https://leetcode.com/problems/car-pooling/
题目:
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 <= 1000
trips[i].length == 3
1 <= trips[i][0] <= 100
0 <= trips[i][1] < trips[i][2] <= 1000
1 <= capacity <= 100000
题解:
For each interval, at start, there are passangers getting on, at end, there are passagers getting off.
Then arrange original interval as start with positive integer of passager count, end with negative integer of passage count.
Sort them based on time. Let negative number come first as they get off, could minimize current passager count.
If current passage count > capacity, return false.
Time Complexity: O(nlogn). n = trips.length.
Space: O(n).
AC Java:
class Solution {
public boolean carPooling(int[][] trips, int capacity) {
if(trips == null || trips.length == 0){
return true;
} List<int []> list = new ArrayList<>();
for(int [] trip : trips){
list.add(new int[]{trip[1], trip[0]});
list.add(new int[]{trip[2], -trip[0]});
} Collections.sort(list, (a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
int count = 0;
for(int [] arr : list){
count += arr[1];
if(count > capacity){
return false;
}
} return true;
}
}
最新文章
- 百度地图API 批量添加 带检索功能的信息窗口
- MFC如何隐藏RibbonBar的QAT QuickAccessToolBar(快速访问工具栏)
- HTML5 UI框架Kendo UI Web教程:创建自定义组件(三)
- svn更新项目时遇到被锁住的问题
- STM32F4_TIM输出PWM波形(可调频率、占空比)
- React可控组件与不可控组件
- 用 SQL 脚本读取Excel 中的sheet数量及名称
- C语言运算符的注意问题
- 读书笔记: 深入浅出node.js
- centos 7安装pycharm
- Kali学习笔记4:Wireshark详细使用方法
- MySQL拓展操作
- Ubuntu中,wxpython的TextCtrl引发的error:_pixman_log_error
- Linux中断管理 (2)软中断和tasklet
- jenkins服务器上安装配置Android SDK
- MVC模式和MVP模式的区别
- 2018-10-19,下午4点拿到京东offer
- Retrieving the COM class factory for component with CLSID {00024500-0000-0000-C000-000000000046} failed due to the following error: 80070005 拒绝访问
- RTP/RTCP 和 SRTP/SRTCP协议(转)
- 微信小程序- wx.request请求不到数据