y*******8
发帖数: 112 | 1 先谢谢各位了！
题目是：Given a set of n jobs with [start time, end time, cost] find a
subset so that no 2 jobs overlap and the cost is maximum.
brute force 肯定是不行的了。我知道一个O(N^2)的解答，请问有更好的答案吗？谢谢
了！ |
d****n
发帖数: 233 | 2 DP吧， 先sort the jobs by end time, if the end time is the same, then by
start time.
Cost[i] = |- Cost[i-1] + JobCost[i] if job i doesn't overalap with previous
jobs
|- Max(Cost[i-1]， Cost[j]+ JobCost[i] where j is the closest job
which is not overlapping with job i
【在 y*******8 的大作中提到】
: 先谢谢各位了！
: 题目是：Given a set of n jobs with [start time, end time, cost] find a
: subset so that no 2 jobs overlap and the cost is maximum.
: brute force 肯定是不行的了。我知道一个O(N^2)的解答，请问有更好的答案吗？谢谢
: 了！
|
c******n
发帖数: 100 | |
y*******8
发帖数: 112 | |
y*******8
发帖数: 112 | 5 恕我愚钝，请问为什么是按照end time sort呢？
previous
job
【在 d****n 的大作中提到】
: DP吧， 先sort the jobs by end time, if the end time is the same, then by
: start time.
: Cost[i] = |- Cost[i-1] + JobCost[i] if job i doesn't overalap with previous
: jobs
: |- Max(Cost[i-1]， Cost[j]+ JobCost[i] where j is the closest job
: which is not overlapping with job i
:
|
j**********g
发帖数: 77 | |
d****n
发帖数: 233 | 7 按endtime的话， 当你处理ith job时， 可以通过binarysearch 很快找到最接近的job
which
is not overlapping with ith job。 因为前面i-1个的endtime是递增的。
【在 y*******8 的大作中提到】
: 恕我愚钝，请问为什么是按照end time sort呢？
:
: previous
: job
|
y*******8
发帖数: 112 | 8 学习了，谢谢！！！
job
【在 d****n 的大作中提到】
: 按endtime的话， 当你处理ith job时， 可以通过binarysearch 很快找到最接近的job
: which
: is not overlapping with ith job。 因为前面i-1个的endtime是递增的。
|
h**********c
发帖数: 4120 | 9 这个题如果time granualarity 比较coarse的话
比如
[3,5] -> ［３，４，５］
［１，７］－＞ ［１，２，３，４，５，６，７］
然后进hash map
有overlap就是weighted graph 的bfs
opinion |
y*******8
发帖数: 112 | 10 先谢谢各位了！
题目是：Given a set of n jobs with [start time, end time, cost] find a
subset so that no 2 jobs overlap and the cost is maximum.
brute force 肯定是不行的了。我知道一个O(N^2)的解答，请问有更好的答案吗？谢谢
了！ |
|
|
d****n
发帖数: 233 | 11 DP吧， 先sort the jobs by end time, if the end time is the same, then by
start time.
Cost[i] = |- Cost[i-1] + JobCost[i] if job i doesn't overalap with previous
jobs
|- Max(Cost[i-1]， Cost[j]+ JobCost[i] where j is the closest job
which is not overlapping with job i
【在 y*******8 的大作中提到】
: 先谢谢各位了！
: 题目是：Given a set of n jobs with [start time, end time, cost] find a
: subset so that no 2 jobs overlap and the cost is maximum.
: brute force 肯定是不行的了。我知道一个O(N^2)的解答，请问有更好的答案吗？谢谢
: 了！
|
c******n
发帖数: 100 | |
y*******8
发帖数: 112 | |
y*******8
发帖数: 112 | 14 恕我愚钝，请问为什么是按照end time sort呢？
previous
job
【在 d****n 的大作中提到】
: DP吧， 先sort the jobs by end time, if the end time is the same, then by
: start time.
: Cost[i] = |- Cost[i-1] + JobCost[i] if job i doesn't overalap with previous
: jobs
: |- Max(Cost[i-1]， Cost[j]+ JobCost[i] where j is the closest job
: which is not overlapping with job i
:
|
j**********g
发帖数: 77 | |
d****n
发帖数: 233 | 16 按endtime的话， 当你处理ith job时， 可以通过binarysearch 很快找到最接近的job
which
is not overlapping with ith job。 因为前面i-1个的endtime是递增的。
【在 y*******8 的大作中提到】
: 恕我愚钝，请问为什么是按照end time sort呢？
:
: previous
: job
|
y*******8
发帖数: 112 | 17 学习了，谢谢！！！
job
【在 d****n 的大作中提到】
: 按endtime的话， 当你处理ith job时， 可以通过binarysearch 很快找到最接近的job
: which
: is not overlapping with ith job。 因为前面i-1个的endtime是递增的。
|
h**********c
发帖数: 4120 | 18 这个题如果time granualarity 比较coarse的话
比如
[3,5] -> ［３，４，５］
［１，７］－＞ ［１，２，３，４，５，６，７］
然后进hash map
有overlap就是weighted graph 的bfs
opinion |
Q**w
发帖数: 41 | 19
job
请教下如果end time有重复值，同一个end time对应不同的cost。。还能二分不？
【在 d****n 的大作中提到】
: 按endtime的话， 当你处理ith job时， 可以通过binarysearch 很快找到最接近的job
: which
: is not overlapping with ith job。 因为前面i-1个的endtime是递增的。
|
m*********t
发帖数: 527 | 20 仔细看了一下文献，这个题目出出来挺坑人的。。。。
http://en.wikipedia.org/wiki/Interval_scheduling
算是 maximum weight independent set 的特殊情形，而且刚刚好有 polynomial time
的解法。。。我觉得没有相关 background 能想出来解法都不错了。。。。 |
