A*e
2 楼
一组区间，不重叠子集最大是多少。感觉是NPC。
【在 H******7 的大作中提到】
: 给定一堆会议的开始以及结束时间，问怎么安排能安排尽可能多的会议。
: 这题目思路是啥？
【在 H******7 的大作中提到】
: 给定一堆会议的开始以及结束时间，问怎么安排能安排尽可能多的会议。
: 这题目思路是啥？
A*e
3 楼
好像贪心法就可以。反证法可以证明，结束时间最早的区间一定在最优解里，否则总可
以把它加进去，替换掉一个。
算法就是每次找剩下区间里，结束时间最早且和当前解法区间不重叠的。
【在 A*******e 的大作中提到】
: 一组区间，不重叠子集最大是多少。感觉是NPC。
以把它加进去，替换掉一个。
算法就是每次找剩下区间里，结束时间最早且和当前解法区间不重叠的。
【在 A*******e 的大作中提到】
: 一组区间，不重叠子集最大是多少。感觉是NPC。
i*h
4 楼
贪心算法就可以。onsite被问过，面试官也是这个观点。
i*h
5 楼
延伸问题还会问 几点到几点的会之间互相的关系，比如B会议必须在A之后开，C也必须
在A之后开，D会议只要B/C其中一个完成后就能开，如果D会议之前开过B会议就可以开E
会议，如果没有就不能开E会议。问排列关系。
在A之后开，D会议只要B/C其中一个完成后就能开，如果D会议之前开过B会议就可以开E
会议，如果没有就不能开E会议。问排列关系。
w*h
6 楼
这题dp也可以
先按照完成时间排序
dp[i] = max(dp[i-1], dp[k] + 1)
其中k是i之前最后一个和i无交集的区间的序号
O(nlogn)时间复杂度
先按照完成时间排序
dp[i] = max(dp[i-1], dp[k] + 1)
其中k是i之前最后一个和i无交集的区间的序号
O(nlogn)时间复杂度
相关阅读
求EMC refer!F家被内推后会收到系统确认email吗？回馈本版--报告一些最近的面筋linkedin上面cs行业top 10毕业学校有人最近办转工作签证么？在附属大公司的小公司工作，简历上可以写在大公司里工作吗？求码工工作内推： Indianapolis, IN, Cincinnati, OH or Dayton, OH.提供亚麻内推150k 涨到180k值得换工作到NYC吗?白人招人没有私心么？fb hire过程多个 H1b 换状态 申请，有点复杂，谢谢大家了OPT什么时候开始新人找工菜鸟问： 办公楼里没手机信号咋办？EE求内推！面试了三轮之后被告知不match换组问题找工作1个星期，已经收到2封拒信麻省 有可以内推的吗? Big Data, Java, Hadoop纽约的18万和硅谷的20万