用最长的作业时间安排时间表。

Question

我正在处理一些问题，我有一些时间设置（开始 - 结束），我必须给出清单，以便最大数量的工作完成。

1. 我有解决方案，我用DP和解决它的On2

可它在做什么？

Answer 1

好吧，我得到了解决它可以通过贪心算法 做详细说明： http://www.cs.umd.edu/class/fall2009/cmsc451/lectures/Lec04-interval.pdf

Answer 2

你让出岗位是J1（S1，E1），J2（S2，E2），...，JN（ sn，en） 其中s1，s2，s3，...，sn是作业的开始时间，而e1，e2，e3，...，en是作业的结束时间。

现在工作根据其开始时间排序（SI的） （使用任何的算法（O（N LG N））。 还要注意作业＃（你或许可以存储作业＃在另一个数组。 当您对作业的开始时间进行排序时，也会对相应的作业＃排列）

现在从列表中选择最后一个作业（现在排序），并将其放入最终答案列表中。

从上一份作业 中以反向方式浏览列表，并在上一份作业有时继续检查可以执行的作业已经被采纳。此作业的结束时间小于或等于上次作业的开始时间。将这份工作添加到您的最终答案列表中。

现在执行此作业的相同程序。从该索引中扫描列表并获取工作，使其结束时间小于或等于上次添加到最终答案列表中的工作的开始时间。重复此操作直到完成。

现在只需计算最终答案列表中的作业数量。 这是可以完成的作业的最大数量。

整个过程需要O（n lg n）+ O（n）时间。 （如果您使用非基于比较的排序算法（如基数排序）对起始时间进行排序，则可以减少这一点，然后复杂度变为O（n））。