求这道面经题的解法

可以formulate 成mixed integer linear programming 问题， 用simplex method 再round 或者branch &bound. 可以从dual, prime 估算最优值区间去掉一些branches

这题我记得可以用pq做，楼主可以上leetcode搜一搜

user123456 发表于 2019-6-11 08:34
感觉greedy似乎不行。给个反例：
Events = [1, 10], [2, 15], [11, 50], [12, 13], [13, 14]
这样Greedy ...

我合计你也没按结束时间排序啊

说到底这道题就是longest increasing subsequence, 你只需要按某一个时间排序即可,  可是我觉得你并不懂.

这个题是为数不多greedy可以直接做的. greedy只是dp的一种特殊情况.

最后, 我跟群主的回答明明一模一样, 为什么不理我的.

user123456 发表于 2019-6-11 17:58
Hmm...这个似乎是在用假设证明基于这个假设的结论

理一下思路：
1. 按照区间的结束时间排序，再沿着结束时间从小到大一次遍历。
2. 在任意一个结束时间上来看，其对应的开始时间一定在前，所以这个区间已经结束，与后面的区间没有瓜葛，所以当选。
3. 如果下一个区间E的开始时间在当前结束时间之前，那么就略过下一个区间。假如考虑E，那么就带来两个问题：第一，必须要考虑这个区间的开始时间位置；第二，结束时间推后，往后的重叠机率更高。