有一个朋友给我说，他说可以解决好于o一个谜（N ^ 3）的时间。

A friend gave me a puzzle that he says can be solved in better than O(n^3) time.

给定一组N个就业机会，每​​有一组开始时间和结束时间（重叠是很可能的），找到最小的子集，对每一项工作或者包括工作或包括曾与该作业重叠的工作。

Given a set of n jobs that each have a set start time and end time (overlaps are very possible), find the smallest subset that for every job either includes that job or includes a job that has overlap with that job.

我是pretty的确保最佳的解决方案是选择工作最无人盯防的重叠，将其添加到解决方案集，然后对它进行标记，其重叠。而重复，直到所有作业都标。 搞清楚哪个作业具有最无人盯防overlappers是一个简单的邻接矩阵（为O（n ^ 2）），这有一个工作选择每次要重做，以更新的标志，使得它为O（n ^ 3 ）。

I'm pretty sure that the optimal solution is to pick the job with the most unmarked overlap, add it to the solution set, then mark it, and its overlap. And repeat until all jobs are marked. Figuring out which job has the most unmarked overlappers is a simple adjacency matrix (O(n^2)), and this has to be redone every time a job is selected, in order to update the marks, making it O(n^3).

有没有更好的解决办法？

Is there a better solution?

推荐答案

让 A 是集工作，我们已经不重叠呢。

Let A be the set of jobs which we haven't overlapped yet.

找到工作 X 在 A 其具有最小结束时间（ T ）。 从所有的工作，其启动时间小于 T ：挑作业Ĵ的最大结束时间。 添加Ĵ的输出设定。 删除所有作业重叠的Ĵ从 A 。 在重复1-4，直到 A 是空的。 Find the job x in A which has the minimal end time (t). From all jobs whose start time is less than t: pick the job j with the maximum end time. Add j to the output set. Remove all jobs which overlap j from A. Repeat 1-4 until A is empty.

一个简单的实施将运行在O（N ^ 2）。使用区间树它可能可以为O解决（N * LOGN）。

A simple implementation will run in O(n^2). Using interval trees it's probably possible to solve in O(n*logn).

后面为什么它是一个最佳的解决方案（不是正式的证明）的基本思想：我们必须选择一份工作，其启动时间小于 T ，使 X 将重叠。如果我们让取值是集合所有的工作，其启动时间小于 T 的，它可以证明Ĵ将重叠同样的工作在取值任何工作，再加上可能更多。因为我们必须选择一份工作在取值，最好的选择是Ĵ。我们可以用这个思路，形成对就业人数的证明用归纳法。

The basic idea behind why it's an optimal solution (not a formal proof): We have to pick one job whose start time is less than t, so that x will be overlapped. If we let S be the set of all jobs whose start time is less than t, it can be shown that j will overlap the same jobs as any job in S, plus possibly more. Since we have to pick one job in S, the best choice is j. We can use this idea to form a proof by induction on the number of jobs.