5k跳水 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>PhotoGear - 摄影器材

5k跳水

5k跳水# PhotoGear - 摄影器材

c*w2011-08-14 07:08

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)

答案是两辆车。

p*e2011-08-14 07:08

2 楼

300586206652

r*y2011-08-14 07:08

3 楼

这个题目原型是meeting room reservation或者railroad，跟merge interval还不太一
样，你只需要求最少的满足条件的数量。

x*02011-08-14 07:08

4 楼

好，我的那个准备退了

【在 p********e 的大作中提到】

: 300586206652

c*w2011-08-14 07:08

5 楼

我觉的这个用merge interval可以做吧。就是sort BY START 一下然后merge的时候取
intersection而不是union。貌似可以。不是很确定

r*v2011-08-14 07:08

6 楼

还是没到你的进价啊。。。

【在 p********e 的大作中提到】

: 300586206652

n*n2011-08-14 07:08

7 楼

2楼说的没错，其实用不着merge interval的方法，就是把start time 于end time混一
起排序，一遍扫描，start就加一 end就减一。

p*e2011-08-14 07:08

8 楼

我的平均进价挺高的也一千零几了

【在 r***v 的大作中提到】

: 还是没到你的进价啊。。。

S*52011-08-14 07:08

9 楼

可是混一起排序的话开始和结束时间不就乱了？有点没看懂

【在 n*******n 的大作中提到】

: 2楼说的没错，其实用不着merge interval的方法，就是把start time 于end time混一
: 起排序，一遍扫描，start就加一 end就减一。

r*v2011-08-14 07:08

10 楼

嗯，你要在医院19XX出的话还真是不到90%的Margin

【在 p********e 的大作中提到】

: 我的平均进价挺高的也一千零几了

j*l2011-08-14 07:08

11 楼

我看着像uber的面经啊。
之前看到有人给答案的，建一个大数组。一天24小时，每小时 60分钟。24*60=1440个
元素代表每一分钟吧。
然后看有没有overlap.
话说建个数组好方便，在好多地方用着也比语言自带的数据结构快。

w*12011-08-14 07:08

12 楼

meeting rooms II
caterpillar算法

s*u2011-08-14 07:08

13 楼

请问如何判断Overlap，
比如说：
（2，5）（3，7）（5，9）
timesheet = [0,0,0,0,0,0,0,0,0] i 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*l2011-08-14 07:08

14 楼

我觉得可以相当于就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 : 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*u2011-08-14 07:08

15 楼

谢谢解释，很清楚。
请问有没有数学方法能证明它永远是对的？

【在 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.