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.
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:
- 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?
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!
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] (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]
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.
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.
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!
Here's the follow-up question.
