g******0
发帖数: 221 | 1 Given a list of presentations with begin and end time that all need to
use a conference room. We want to optimize the utilization of the room
by allowing maximum hours of the conference room being used.
Note: Not optimizing for the maximum number of presentations (This
would be the greedy algorithm from the CLRS book).
Any idea? | d*******d
发帖数: 2050 | | g**e
发帖数: 6127 | 3 背包问题
【在 g******0 的大作中提到】
: Given a list of presentations with begin and end time that all need to
: use a conference room. We want to optimize the utilization of the room
: by allowing maximum hours of the conference room being used.
: Note: Not optimizing for the maximum number of presentations (This
: would be the greedy algorithm from the CLRS book).
: Any idea?
| c*******n
发帖数: 63 | 4 could somebody prove that we can generate an optimal solution if occupied
hours (end time - begin time) are used for greedy choices? | s*****y
发帖数: 897 | 5 [0,2] [3,12][14,15] [3,7][8,15]
greedy will be [0,2] [3,12][14,15]
but best should be [0,2][3,7][8,15]
【在 c*******n 的大作中提到】
: could somebody prove that we can generate an optimal solution if occupied
: hours (end time - begin time) are used for greedy choices?
| c*******n
发帖数: 63 | 6 Nice work!
then we should try DP
【在 s*****y 的大作中提到】
: [0,2] [3,12][14,15] [3,7][8,15]
: greedy will be [0,2] [3,12][14,15]
: but best should be [0,2][3,7][8,15]
| g**********y
发帖数: 14569 | 7 写了一个ugly的实现，想法是把presentation按结束时间排序。最后结束时间T，M[0..
T]记录时间0..t的最大利用值。
M[A(n,1)] = max{A(n,1)-A(n,0)+max(M[0..A(n,0)]), max(M[0..A(n,1)])}
程序应该可以简化，要输出选择的presentation, 数据结构也要改。
public void maxUse(List list) {
Collections.sort(list, new Comparator() {
public int compare(int[] a, int[] b) {
return a[1] - b[1];
}
});
int N = list.size();
int T = list.get(N-1)[1];
int[] max = new int[T+1];
for (int i=0; i
int[] a = list.get(i);
int v1 = getMax(max, a[1]);
int v2 = a[1] - a[0] + getMax(max, a[0]-1);
max[a[1]] = Math.max(v1, v2);
}
System.out.println(max[T]);
}
private int getMax(int[] max, int t) {
for (int i=t; i>=0; i--) {
if (max[i] > 0) return max[i];
}
return 0;
} | g******0
发帖数: 221 | 8 Yes, true dat!
【在 d*******d 的大作中提到】
: I guess dp will do
| m**q
发帖数: 189 | 9 程序有点没看懂，看描述复杂度是O(n^2)?
这题应该可以O(nlgn)的
..
【在 g**********y 的大作中提到】
: 写了一个ugly的实现，想法是把presentation按结束时间排序。最后结束时间T，M[0..
: T]记录时间0..t的最大利用值。
: M[A(n,1)] = max{A(n,1)-A(n,0)+max(M[0..A(n,0)]), max(M[0..A(n,1)])}
: 程序应该可以简化，要输出选择的presentation, 数据结构也要改。
: public void maxUse(List list) {
: Collections.sort(list, new Comparator() {
: public int compare(int[] a, int[] b) {
: return a[1] - b[1];
: }
: });
| i**d
发帖数: 357 | 10
你这个greedy的取值条件不对。
应该是首先按照结束时间排序，然后greedy的每次取最早结束的presentation.
并且remove有overlap的presentation
按照这个例子应该首先排序成
[0,2],[3,7],[3,12],[8,15],[14,15]
首先取 [0,2]
然后取 [3,7] 并remove有overlap的[3,12]
最后取 [8,15], 并remove掉[14,15]
结果就是[0,2],[3,7],[8,15]
【在 s*****y 的大作中提到】
: [0,2] [3,12][14,15] [3,7][8,15]
: greedy will be [0,2] [3,12][14,15]
: but best should be [0,2][3,7][8,15]
| H****s
发帖数: 247 | 11 这题就是 weighted interval scheduling 吧。 每个conference 的 weight就是它的
长度， 然后要求就总weight最大。 DP 就可解一般O(n^2), 使用特殊数据结构可以O(
nlgn) | d*******l
发帖数: 338 | 12 对，都不用什么特殊数据结构。按结束时间排序，d[i]表示前i个可以取到的最大时间
。对每个i，找到第一个满足start[i]>=end[j]的j，d[i]=max(d[i-1],d[j]+length[i]). 查找的过程用二分可以做到logn.
【在 H****s 的大作中提到】
: 这题就是 weighted interval scheduling 吧。 每个conference 的 weight就是它的
: 长度， 然后要求就总weight最大。 DP 就可解一般O(n^2), 使用特殊数据结构可以O(
: nlgn)
| P**l
发帖数: 3722 | 13 dp吧
给个greedy的反例：
[0,2][3,4][1,100] |
|
