问一道题(2) - 未名空间MITBBS历史存档

f*i2011-05-18 07:05

1 楼

有一堆的工作,每个工作有开始和结束时间,假设表示为[2,3],[3,7]等等,现在要求在[1
,n]的时间段内选出尽可能多的工作.
如果用按照开始时间排序的方法,greedy是无法保证最多的.我也考虑过把这些interval
按照开始和结束时间分别排序,然后比较,但是这个本质上也还是greedy.
一种方法是找出所有interval的combination,用recursive写程序是很简单,但是时间复
杂度太高了,虽然很多情况可以减枝.
求高人解答

g*s2011-05-18 07:05

2 楼

not understand the question. could you explain more detail?

[1
interval

【在 f*********i 的大作中提到】

: 有一堆的工作,每个工作有开始和结束时间,假设表示为[2,3],[3,7]等等,现在要求在[1
: ,n]的时间段内选出尽可能多的工作.
: 如果用按照开始时间排序的方法,greedy是无法保证最多的.我也考虑过把这些interval
: 按照开始和结束时间分别排序,然后比较,但是这个本质上也还是greedy.
: 一种方法是找出所有interval的combination,用recursive写程序是很简单,但是时间复
: 杂度太高了,虽然很多情况可以减枝.
: 求高人解答

d*l2011-05-18 07:05

3 楼

greedy确实是不对的，有O(nlogn)的dp做法

[1
interval

【在 f*********i 的大作中提到】

: 有一堆的工作,每个工作有开始和结束时间,假设表示为[2,3],[3,7]等等,现在要求在[1
: ,n]的时间段内选出尽可能多的工作.
: 如果用按照开始时间排序的方法,greedy是无法保证最多的.我也考虑过把这些interval
: 按照开始和结束时间分别排序,然后比较,但是这个本质上也还是greedy.
: 一种方法是找出所有interval的combination,用recursive写程序是很简单,但是时间复
: 杂度太高了,虽然很多情况可以减枝.
: 求高人解答

s*y2011-05-18 07:05

4 楼

他的greedy是每次完成一个工作以后然后选择最先开始的继续？
这题跟这个里面的例子有啥不一样啊。
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=greedy

c*w2011-05-18 07:05

5 楼

这个是一个经典的用贪婪法解决的问题。把所有的时间段先根据结束时间排序，然后
用一个一个按照结束时间的先后来找可行的时间段...........

h*n2011-05-18 07:05

6 楼

怎么“一个一个”找呢？DP么？

【在 c******w 的大作中提到】

: 这个是一个经典的用贪婪法解决的问题。把所有的时间段先根据结束时间排序，然后
: 用一个一个按照结束时间的先后来找可行的时间段...........

f*i2011-05-18 07:05

7 楼

问题是这样的
有一堆intervals [1,8],[2,4],[3,6],[4,7],[8,9], 要求在[1,10]的范围内找出最多
不overlap的interval,在这题里面,是[2,4],[4,7],[8,9]
如果是按照开始,或者结束时间排序的话,是没有办法保证最优解的.
有什么好办法吗?

a*n2011-05-18 07:05

8 楼

没有细看，不过这个好像是CLRS讲贪婪算法时的例题吧？

[1
interval

【在 f*********i 的大作中提到】

: 有一堆的工作,每个工作有开始和结束时间,假设表示为[2,3],[3,7]等等,现在要求在[1
: ,n]的时间段内选出尽可能多的工作.
: 如果用按照开始时间排序的方法,greedy是无法保证最多的.我也考虑过把这些interval
: 按照开始和结束时间分别排序,然后比较,但是这个本质上也还是greedy.
: 一种方法是找出所有interval的combination,用recursive写程序是很简单,但是时间复
: 杂度太高了,虽然很多情况可以减枝.
: 求高人解答

s*y2011-05-18 07:05

9 楼

你看看我帖的那个top coder的tourial，不就是可以解答这个问题了吗？
一摸一样的，贪婪，先去选择最先结束的，那么你就可以有更多剩余时间干其他的。

【在 f*********i 的大作中提到】

: 问题是这样的
: 有一堆intervals [1,8],[2,4],[3,6],[4,7],[8,9], 要求在[1,10]的范围内找出最多
: 不overlap的interval,在这题里面,是[2,4],[4,7],[8,9]
: 如果是按照开始,或者结束时间排序的话,是没有办法保证最优解的.
: 有什么好办法吗?

f*42011-05-18 07:05

10 楼

clsr 16.1

c*w2011-05-18 07:05

11 楼

可以看看这个链接吧。 http://www.cs.uiuc.edu/class/fa05/cs473g/lectures/06-greedy.pdf。后面还有个证明：Theorem 4. The greedy schedule is an optimal schedule.

【在 f*********i 的大作中提到】

: 问题是这样的
: 有一堆intervals [1,8],[2,4],[3,6],[4,7],[8,9], 要求在[1,10]的范围内找出最多
: 不overlap的interval,在这题里面,是[2,4],[4,7],[8,9]
: 如果是按照开始,或者结束时间排序的话,是没有办法保证最优解的.
: 有什么好办法吗?

d*l2011-05-18 07:05

12 楼

后来又想了想，如果这题每个工作都认为是具有相同价值的，确实就是贪心法的例题。
。。我之前遇到过的是每个工作还有个权值，让找出总权值最大的方案，这就能用到O(
nlogn)的dp了

f*i2011-05-18 07:05

13 楼

问了三个问题,第一个题目还算靠谱,就是在arraylist里面有乱序的数字,如何找出两个
数字使得和为0, O(n), 然后如何找出三个数字和为0, O(n^2), 四个数字和为0,这里我
卡了一下,在提示后给出了O(n^2)的解,然后如何找出五个数字和为0,我给出了O(n^3)的
解.
第二个问题就比较郁闷了,他说,假设在有人创建了一个linkedIn account,如何从他的
profile里面得出信息以便给出推荐,such as, people you may know, job you may
like, something you may interested.
我回答key word matching, 然后他问如何判断什么word是keyword, 如何pattern
match,如何text selection, 还有如何train出classification rule,等等等等,,,,我
侃了一大堆data mining方面的东西,感觉他不满意.
最后一个问题问我GPA.......
觉得很郁闷啊,如果倒在算法上也就算了,但是给出个这么笼统的东西叫我当场设计不是
为难人吗....

f*i2011-05-18 07:05

14 楼

发错了,准备开新贴的...

m*q2011-05-18 07:05

15 楼

假设每个任务开始结束为start[i], end[i],对应的权值为a[i],
先把数组按start[i]排序，设从i...n的工作中，总的最大权值为f[i],则：
f[i] = max { f[i+1], a[i] + f[k]: k是i之后和i不冲突的第一个元素 }
排序O(nlgn),遍历a[]数组O（n),对每个元素i用二分法找对应的k，O(lgn),
总复杂度为O(nlgn)。
这个方法对不？

O(

【在 d*******l 的大作中提到】

: 后来又想了想，如果这题每个工作都认为是具有相同价值的，确实就是贪心法的例题。
: 。。我之前遇到过的是每个工作还有个权值，让找出总权值最大的方案，这就能用到O(
: nlogn)的dp了

d*l2011-05-18 07:05

16 楼

对。如果按开始时间排序的话就得i从大到小循环，不过思路就是这样没错。

【在 m**q 的大作中提到】

: 假设每个任务开始结束为start[i], end[i],对应的权值为a[i],
: 先把数组按start[i]排序，设从i...n的工作中，总的最大权值为f[i],则：
: f[i] = max { f[i+1], a[i] + f[k]: k是i之后和i不冲突的第一个元素 }
: 排序O(nlgn),遍历a[]数组O（n),对每个元素i用二分法找对应的k，O(lgn),
: 总复杂度为O(nlgn)。
: 这个方法对不？
:
: O(

s*c2011-05-18 07:05

17 楼

按结束时间排序可以给出最优解呀～
[2,4]后面跟着[3,6]，但是[3,6]的开始时间和[2,4]overlap了，所以应该选[4,7]，然
后以此类推。。。。。

【在 f*********i 的大作中提到】

: 问题是这样的
: 有一堆intervals [1,8],[2,4],[3,6],[4,7],[8,9], 要求在[1,10]的范围内找出最多
: 不overlap的interval,在这题里面,是[2,4],[4,7],[8,9]
: 如果是按照开始,或者结束时间排序的话,是没有办法保证最优解的.
: 有什么好办法吗?

m*q2011-05-18 07:05

18 楼

谢谢确认;)
或者就是按结束时间排序然后i从小到大，就像你说的

【在 d*******l 的大作中提到】

: 对。如果按开始时间排序的话就得i从大到小循环，不过思路就是这样没错。