c********w
发帖数: 308 | 1 一个租车服务，给你N个intervals, 每个代表客户需要车的start time, end time. 如
果不想让客户等，最少需要准备多少辆车？
(1:00, 02:00)
(16:00, 21:30)
(09:30, 13:00)
(21:00, 22:30)
(12:00, 12:30)
答案是两辆车。 | r*******y
发帖数: 270 | 2 这个题目原型是meeting room reservation或者railroad，跟merge interval还不太一
样，你只需要求最少的满足条件的数量。 | c********w
发帖数: 308 | 3 我觉的这个用merge interval可以做吧。就是sort BY START 一下然后merge的时候取
intersection而不是union。貌似可以。不是很确定 | n*******n
发帖数: 446 | 4 2楼说的没错，其实用不着merge interval的方法，就是把start time 于end time混一
起排序，一遍扫描，start就加一 end就减一。 | S**********5
发帖数: 896 | 5 可是混一起排序的话开始和结束时间不就乱了？有点没看懂
【在 n*******n 的大作中提到】
: 2楼说的没错，其实用不着merge interval的方法，就是把start time 于end time混一
: 起排序，一遍扫描，start就加一 end就减一。
| j*****l
发帖数: 1624 | 6 我看着像uber的面经啊。
之前看到有人给答案的，建一个大数组。一天24小时，每小时 60分钟。24*60=1440个
元素代表每一分钟吧。
然后看有没有overlap.
话说建个数组好方便，在好多地方用着也比语言自带的数据结构快。 | w*****1
发帖数: 6807 | 7 meeting rooms II
caterpillar算法 | s*********u
发帖数: 18 | 8 请问如何判断Overlap，
比如说：
（2，5）（3，7）（5，9）
timesheet = [0,0,0,0,0,0,0,0,0] i <- 0 to 8
when (2, 5) set timesheet[1] to timesheet[4] with 1?
[0, 1, 1, 1, 1, 0, 0, 0, 0]
When (3, 7), how do i know if there is a overlap?
Thanks.
【在 j*****l 的大作中提到】
: 我看着像uber的面经啊。
: 之前看到有人给答案的，建一个大数组。一天24小时，每小时 60分钟。24*60=1440个
: 元素代表每一分钟吧。
: 然后看有没有overlap.
: 话说建个数组好方便，在好多地方用着也比语言自带的数据结构快。
| j*****l
发帖数: 1624 | 9 我觉得可以相当于就count吧
起始：
[0,0,0,0,0,0,0,0,0]
(2, 5)
[0,0,1,1,1,0,0,0,0]
（3，7）
[0,0,1,2,2,1,1,0,0]
（5，9）
[0,0,1,2,2,2,2,1,1]
每一个元素不是代表clock 2, 3, 而是代表time period.
第一个元素是从0到1, 第二个元素是从1到2，最后一个元素是从8到9.
所以写【2,5】的时候就是把从2到3，从3到4，从4到5的元素+1.
这样是最终算出来最大count是2就是两辆车吧。
【在 s*********u 的大作中提到】
: 请问如何判断Overlap，
: 比如说：
: （2，5）（3，7）（5，9）
: timesheet = [0,0,0,0,0,0,0,0,0] i <- 0 to 8
: when (2, 5) set timesheet[1] to timesheet[4] with 1?
: [0, 1, 1, 1, 1, 0, 0, 0, 0]
: When (3, 7), how do i know if there is a overlap?
: Thanks.
| s*********u
发帖数: 18 | 10 谢谢解释，很清楚。
请问有没有数学方法能证明它永远是对的？
【在 j*****l 的大作中提到】
: 我觉得可以相当于就count吧
: 起始：
: [0,0,0,0,0,0,0,0,0]
: (2, 5)
: [0,0,1,1,1,0,0,0,0]
: （3，7）
: [0,0,1,2,2,1,1,0,0]
: （5，9）
: [0,0,1,2,2,2,2,1,1]
: 每一个元素不是代表clock 2, 3, 而是代表time period.
|
|
