H******7
发帖数: 1728 | 1 给定一堆会议的开始以及结束时间，问怎么安排能安排尽可能多的会议。
这题目思路是啥？ |
A*******e
发帖数: 2419 | 2 一组区间，不重叠子集最大是多少。感觉是NPC。
【在 H******7 的大作中提到】
: 给定一堆会议的开始以及结束时间，问怎么安排能安排尽可能多的会议。
: 这题目思路是啥？
|
A*******e
发帖数: 2419 | 3 好像贪心法就可以。反证法可以证明，结束时间最早的区间一定在最优解里，否则总可
以把它加进去，替换掉一个。
算法就是每次找剩下区间里，结束时间最早且和当前解法区间不重叠的。
【在 A*******e 的大作中提到】
: 一组区间，不重叠子集最大是多少。感觉是NPC。
|
i*****h
发帖数: 1534 | 4 贪心算法就可以。onsite被问过，面试官也是这个观点。 |
i*****h
发帖数: 1534 | 5 延伸问题还会问 几点到几点的会之间互相的关系，比如B会议必须在A之后开，C也必须
在A之后开，D会议只要B/C其中一个完成后就能开，如果D会议之前开过B会议就可以开E
会议，如果没有就不能开E会议。问排列关系。 |
w*****h
发帖数: 423 | 6 这题dp也可以
先按照完成时间排序
dp[i] = max(dp[i-1], dp[k] + 1)
其中k是i之前最后一个和i无交集的区间的序号
O(nlogn)时间复杂度 |
