Re: Generating an optimum sequence of tasks

Steve Schwartz wrote:
I'm hoping someone says something like "Obviously. Use the pigeonhole principle." but I don't really understand that stuff. Actually, I would prefer a nice O(n) or O(nlog(n)) solution but I'm not very hopeful. My real world values for n are in the hundreds up to maybe 1000.

Thanks in advance for the help.

for i from 1 to n
for j from 1 to i
do task i
do task j

i j

1 1

2 1
2 2

3 1
3 2
3 3

4 1
4 2
4 3
4 4

....

Do you see why it works?

It's like thinking of the multiplication table and realizing you need only half of it because a*b = b*a. If you need 7*5 you look up 5*7, i.e. you only need the entries (i,j) with i<=j.

Kiuhnm
.

Quantcast