这个问题是灵感来自工艺配置另一个问题。这是一种扭曲，并增强，讨论存在的问题。

This question is inspired by another question on process allocation. This is a twist on, and enhancement of, the problem discussed there.

我们拥有的 N 的进程，我们需要将它们分配给尽可能少的处理器。每个进程都有一个预定的开始和结束时间，我们将在来定义时间单位的，从1索引;一个进程运行一段连续的时间单位序列。处理器可以被安排运行任意数量的非重叠的过程。

We have n processes, and we need to allocate them to the fewest possible processors. Each process has a scheduled start and finish time, which we will define in terms of time units, indexed from 1; a process will run for some contiguous sequence of time units. A processor can then be scheduled to run any number of non-overlapping processes.

最明显的贪心算法是：

目前的每个步骤，安排一个最大非重叠组的其余过程到下一处理器。

At each step, schedule a maximal non-overlapping set of the remaining processes onto the next processor.

如何是一个最大的非重叠设置为被选择？我们将离开算法的非确定性的，因为这可以更容易地分析并分成两个子问题

How is a maximal non-overlapping set to be chosen? We will leave the algorithm as non-deterministic, since that makes it easier to analyse and split into two sub-questions.

从本质上讲，previous有关问题提出的行为，如果该算法的吉利的：什么是最小的 N 的针对此算法的也许的生产次最佳分配（即，比必要要求一个以上处理器）？事实证明，答案是的 N 的= 4。有在两个处理器足够的情况下，但贪心算法的可能的需要三个处理器（不过，如果它是幸运的，它会做的两个步骤）。

Essentially, the previous question concerned behaviour if the algorithm is unlucky: what's the smallest n for which this algorithm might produce a sub-optimal allocation (i.e., require more processors than necessary)? It turns out that the answer is n=4. There are cases where two processors are sufficient, but the greedy algorithm might require three processors (though if it's lucky, it will do it in two steps).

这个问题涉及到如果非决定论是什么情况永远的吉利的：

This question concerns what happens if the non-determinism is always lucky:

什么是最小的 N 的针对此算法的保证的次优？也就是说，什么是最小的 N 的对，我们可以找到一组进程，其中的贪心算法的必须的使用超过必要的流程？

What's the smallest n for which this algorithm is guaranteed to be sub-optimal? That is, what's the smallest n for which we can find a set of processes where the greedy algorithm must use more processes than necessary?

由于堆栈溢出积极鼓励提出和回答你自己的问题，我将这样做在这里，你能告诉我是否我的部分答案可以改进！

Since Stack Overflow actively encourages asking and answering your own question, I will do so here, and you can tell me whether my partial answer can be improved upon!

推荐答案

我的认为的答案是的 N 的= 7。我会努力证明某些事情出错的 N 的= 7;但这只是给出了一个上界。事情可能出错的 N = 6？我不这么认为，但我不知道。

I think that the answer is n=7. I will try to demonstrate that things go wrong with n=7; but this only gives an upper bound. Can things go wrong with n=6? I don't think so, but I'm not sure.

假设我们有以下进程时间表：

Suppose that we have the following processes to schedule:

[1] （即，在此过程中单位时间1运行） [2] [4] [5] [1,2,3] （即，在此过程中的时间单位1至3运行） [2,3,4] [3,4,5] [1] (i.e., the process runs during time unit 1) [2] [4] [5] [1,2,3] (i.e., the process runs during time units 1 to 3) [2,3,4] [3,4,5]

优化配置看起来需要三个处理器：

The optimal allocation looks to require three processors:

[1] ， [2,3,4] [2] ， [3,4,5] [1,2,3] ， [4] ， [5] [1], [2,3,4] [2], [3,4,5] [1,2,3], [4], [5]

但贪心算法将产生如下：

But the greedy algorithm will produce the following:

[1] ， [2] ， [4] ， [5] [1,2,3] [2,3,4] [3,4,5] [1], [2], [4], [5] [1,2,3] [2,3,4] [3,4,5]

这里的关键点是，它会在第一个步骤安排四（因为它是贪婪），并在那之后我们只剩下三个两两重叠的过程。

The key point here is that it'll schedule four on the first step (because it's greedy), and then after that we're left with three pairwise overlapping processes.

可事情出差错的 N = 6？我不这么认为，但我不能肯定。在我看来，就像有关情况将是其中最佳的解决方案需要三个处理器，每个处理器上运行两个过程。我们可以发现其中第一个处理器上的贪心算法调度三，然后只剩下三个重叠的过程，因此需要四个处理器的总？的情况下

Can things go wrong with n=6? I don't think so, but I am not certain. It looks to me as though the relevant case will be where the optimal solution requires three processors, each running two processes. Can we find a case where the greedy algorithm schedules three on the first processor, and is then left with three overlapping processes, thus requiring four processors in total?

我们将需要三双，为的最佳解决方案;但我们需要这些流程，以这样的方式来构造，如果你的第一步安排他们三个人，就可以不那么完整的分为两步骤。显然，这三个过程中不能包括一个对，否则该解决方案可以继续，因为它要同做对，但留给他们一个作为一个单身。因此必须采取一从每个对的

We'll need three pairs, for the optimal solution; but we'll need these processes to be constructed in such a way that if you schedule three of them on the first step, you can't then complete in two steps. Clearly these three processes can't include one of the pairs, or else the solution can continue as it would have done with the pairs, but leaving one of them as a singleton. So it must take one from each of the pairs.

如果一个进程可能需要不连续的时间段，我们能做到这一点是这样的：

If a process could require non-contiguous time blocks, we could do it like this:

[1] [2] [3] [1,2] [2,3] [1,3] （这是不允许的，因为它停止并再次开始！） [1] [2] [3] [1,2] [2,3] [1,3] (this isn't allowed, because it stops and starts again!)

最佳的解决方案将每个配对的单身其补充;贪心算法将采取所有的单身人士一起上了第一步，那么我们就只剩下两两重叠的过程将需要三个以上的处理器。但是，我们已经被骗了，因为上面列出的最后一个过程不为连续时间块运行。

The optimal solution would pair each singleton with its complement; the greedy algorithm would take all the singletons together on the first step, and then the pairwise overlapping processes we're left with would require three more processors. But we've cheated, because the last process listed above doesn't run for a contiguous time block.

我们无法改变的最后一个 [3,4] ，因为那样的话就可以在同一处理器上的运行[1 ，2] 。事实上，我们不能有三个两两重叠的连续的块，除非它们的交集非空。因此，我们最终会喜欢的东西 [1,2,3] ， [2,3,4] ， [3,4,5] ，因为我们与七个流程案例。的问题是，它然后似乎是不可能的添加可被一起调度三个过程，并仍然允许三处理器最优解，而不允许用于调度两个单身与三元之一的可能性。如果我们尝试

We can't change the last one to [3,4], because then it can be run on the same processor as [1,2]. In fact, we can't have three pairwise overlapping contiguous blocks unless their intersection is non-empty. So we'd end up with something like [1,2,3], [2,3,4], [3,4,5], as we had with the seven process case. The problem is that it then seems to be impossible to add three more processes that can be scheduled together, and still allow a three-processor optimal solution, without allowing for the possibility of scheduling two of the singletons with one of the triples. If we try

[1] [2] [4] [1,2,3] [2,3,4] [3,4,5] [1] [2] [4] [1,2,3] [2,3,4] [3,4,5]

那么贪心算法的也许的时间表 [1] ， [2] ， [3,4,5] 的第一步，这将导致一个最佳的解决方案（我们正在寻找一个情况下，非决定论是的保证的导致次优的解决方案）。

then the greedy algorithm might schedule [1], [2], [3,4,5] on the first step, which will lead to an optimal solution (and we're looking for a case where the non-determinism is guaranteed to lead to a sub-optimal solution).

如果我们试图

[2] [3] [4] [1,2,3] [2,3,4] [3,4,5] [2] [3] [4] [1,2,3] [2,3,4] [3,4,5]

然后我们没有对三个处理器的最佳解决方案，因为4的处理的需要时间单元3

then we don't have an optimal solution on three processors, because four of the processes require time unit 3.

所有这些沉思的建议，我认为贪心算法将是最佳的情况下的 N = 6，并且该上限的 N 的= 7因此严格;但它属于相当短的一个证明。我们怎样才能证明它总是最适合的 N = 6？

All of this musing suggests to me that the greedy algorithm will be optimal in the case of n=6, and that the upper bound of n=7 is therefore strict; but it falls rather short of a proof. How can we prove that it's always optimal for n=6?