我读了算法的一些材料，并遇到了一个问题。

I read some material on Algorithms, and ran into a problem.

我们拥有的 N 的过程中，每一个predetermined开始和结束时间。我们要使用以运行所有这些进程的处理器的最小数目

We have n processes, each with a predetermined start and end time. We want to use the minimum number of processors in order to run all these processes.

考虑如下的算法：

在步的我的，选择不重叠目前未分配过程的最大数量，并将它们分配给处理器的我的。

In step i, select maximum number of currently unallocated processes that don't overlap, and allocate them to processor i.

此算法结束时，没有进程仍然未分配的。最大的我的是该算法的输出。是什么的最小值的 N 的，使得该算法并不产生最佳答案？

This algorithm finishes when no processes remain unallocated. The maximum i is the output of this algorithm. What is the minimum value of n such that this algorithm does not produce an optimal answer?

简短的回答： N = 5。我不知道这个答案是如何到达，虽然。你能解释一下吗？

Short answer: n=5. I don't know how this answer is reached, though. Can you explain?

推荐答案

你在这里是一个的贪心算法的。贪婪算法做最好的它可以在每一个步骤，希望这会给出一个最佳解决方案的整体。它通常产生快速算法，和它的有时的，但不总是导致最佳的解决方案。

What you have here is a greedy algorithm. A greedy algorithm does the best it can at each step, in the hope that this will give an optimal solution overall. It usually gives a fast algorithm, and it sometimes, but not always, leads to an optimal solution.

您的算法是一个贪心算法，有时提供了一个最佳的解决方案的一个很好的例子，有时不会。它有它运行快给人一种近似最优解的优势;这有时比一个非常缓慢的算法给出了最佳的解决方案好。

Your algorithm is a good example of a greedy algorithm that sometimes provides an optimal solution and sometimes doesn't. It has the advantage that it runs fast in giving an approximation to an optimal solution; that's sometimes better than a very slow algorithm that gives an optimal solution.

有一个在你的问题的一个重要不确定性。你说的步骤的我的你应该选择可以安排在处理器其余进程的最大数量的我的。让我们假设的过程，可安排在此刻的最大数量为2。如果有很多选择2个非重叠的流程方式？我们如何决定哪2个进程？

There's an important ambiguity in your question. You say that on step i you should choose the maximum number of the remaining processes that can be scheduled on processor i. Let's suppose that the maximum number of processes that can be scheduled at the moment is 2. What if there are lots of ways of choosing 2 non-overlapping processes? How do we decide which 2 processes?

我要认真解决的模糊性，通过边踩着它。比方说，算法会的不确定性的选择极大一整套流程来安排当前的处理器上。这意味着我们可以再打开你的问题分成两个不同的：

I'm going to resolve the ambiguity carefully, by side-stepping it. Let's say that the algorithm will non-deterministically choose a maximal set of processes to schedule on the current processor. That means that we can then turn your question into two different ones:

什么是最小的 N 的针对此算法的也许的是次优？也就是说，假设该算法是不吉利在其选择的最大集。如何能迅速出问题？ 什么是最小的 N 的针对此算法的保证的次优？也就是说，假设该算法总是幸运的，选择合适的最大集合，如果有一个。如何能迅速的东西然后去了？ What's the smallest n for which this algorithm might be sub-optimal? That is, let's suppose the algorithm is unlucky in its choice of maximal set. How quickly can things go wrong? What's the smallest n for which this algorithm is guaranteed to be sub-optimal? That is, let's suppose the algorithm is always lucky, and chooses the right maximal set if there is one. How quickly can things then go wrong?

您声明的 N 的= 4告诉我，你是跨preting它作为第一个问题。我的认为的第二个问题有答案的 N 的= 7，虽然我不能肯定。这是一个有趣的问题不够，我想我会问一个跟进的问题与我的想法有关！

Your statement that n=4 tells me that you're interpreting it as the first question. I think the second question has an answer of n=7, though I'm not certain. This is an interesting enough issue that I think I will ask a follow-up question with my thoughts about that!

下面是如何地看到，事情都可能出错，如果我们不走运，用的 N 的= 4。让我们来谈谈在时间单位上。在这个例子中，我们会说，有四个时间单位（四小时一天，如果你喜欢，每个过程需要的时间，并开始在小时完成一个整数）。让我们假设我们有四个过程，我们需要运行：

Here's how to see that things can go wrong, if we're unlucky, with n=4. Let's talk in terms of time units. For this example, we'll say that there are four time units (four hours of the day, if you like, and each process takes a whole number of hours, starting and finishing on the hour). Let's suppose we have four processes we need to run:

[1] （即过程只需要在第一时间单元） [2,3,4] （即过程需要时间单位2〜4） [1,2,3] （等） [4] [1] (i.e., the process just takes the first time unit) [2,3,4] (i.e., the process needs time units 2 to 4) [1,2,3] (etc.) [4]

现在，还有的认为只有两个处理器的工作分配。在第一个处理器，我们执行 [1] 和 [2,3,4] ;第二个处理器上我们运行 [1,2,3] 和 [4] 。而我们的贪心算法的也许的找到这个解决方案，给我们一些优化。但它的可能的时间表 [1] 和 [4] 来第一个处理器上运行，因为这也是最大集合（它把两个进程在第一处理器）。如果是这样的话，那么它的左与 [1,2,3] 和 [2,3,4] ，不能同时运行，所以它会最终使用三款处理器。

Now, there's an allocation that works with just two processors. On the first processor we run [1] and [2,3,4]; on the second processor we run [1,2,3] and [4]. And our greedy algorithm might find this solution and give us something optimal. But it might schedule [1] and [4] to run on the first processor, since this is also a maximal set (it puts two processes onto the first processor). If it does so, then it's left with [1,2,3] and [2,3,4], which can't be run together, so it'll end up using three processors.

这可能会出错，然后，用的 N 的= 4。它可能出错的 N 的= 3？我不认为如此。有三种可能什么最佳的解决方案可能是这样的：它只需要1个处理器，或2个处理器，或3处理器。如果最佳解决方案只需要1个处理器，则这意味着所有三个过程就可以安排在第一步骤中，我们的贪婪算法将发现此解决方案。如果需要3个处理器，则没有两个进程可以安排在相同的时间，所以贪婪算法将安排一次一个，并将再次找到最佳（3处理器）溶液。如果需要2个处理器，则它必须是2的处理的可以一起运行。如果这是正确的，但是，那么贪心算法将选择在第一步两个过程。取其2它选择，将有只有一个左侧，这将被安排在第二步骤。因此，贪心算法将需要2个处理器，这又是最优的。

It can go wrong, then, with n=4. Can it go wrong with n=3? I don't think so. There are three possibilities for what the optimal solution might look like: it needs only 1 processor, or 2 processors, or 3 processors. If the optimal solution requires only 1 processor, then that means all three processes can be scheduled at the first step, and our greedy algorithm will find this solution. If it takes 3 processors, then no two processes can be scheduled at the same time, so the greedy algorithm will schedule one at a time, and will again find the optimal (3 processor) solution. If it takes 2 processors, then it must be that two of the processes can be run together. If that's right, though, then the greedy algorithm will choose two processes at the first step. Whichever two it chooses, there will be only one left, and this will be scheduled at the second step. So the greedy algorithm will require 2 processors, which is again optimal.

正如我所说，我认为乐观情况下更是有趣：什么是最小的 N 的针对此算法的保证的次优？我会问有关的后续问题，并链接到一个！

As I say, I think the optimistic case is even more interesting: what's the smallest n for which this algorithm is guaranteed to be sub-optimal? I will ask a follow-up question about that, and link to this one!

这里是跟进质询。