The problem goes like this (translated):
There are n (n <= 25000) people at the bottom of a mountain, and everyone wants to go up, then down the mountain. There are 2 tour guides: one for helping a person go up the mountain, one for helping a person go down. Person i takes up(i) time to climb this mountain, and down(i) time to descend it. However, each guide can only help 1 person at a time (which means at most 1 person can be climbing, and at most 1 person can be descending the mountain at any given time). Assume when the "up" guide reaches the top, he gets instantly teleported back to the bottom, as with the "down" guide. Find the least time it takes to get everyone up and back down the mountain. (People can congregate at the top of the mountain if necessary)
Here's a sample input for the problem, with annotations by me:
3 persons
person 1: up=6 minutes, down=4 minutes
person 2: up=8 minutes, down=1 minutes
person 3: up=2 minutes, down=3 minutes
Output to the input:
Minimum amount of time is 17. This is because If person 3 goes first, then person 1, and then person 2 (and this same order is used for both the ascent and descent), this gives a total time of 17.
I've tried coming up with a few algorithms, but here's what I have so far:
An O(n! * n) algorithm: just permute the cows through all possible permutations using next_permutation
A greedy algorithm: I've sorted the people by decreasing descending time, and tried placing them together, but this did not result in the right solution.
Other thoughts
I'm turning to dynamic programming now, as according to the CLR, optimization problems are usually greedy or dynamic programming (this problem , I think, satisfies optimal substructure).
I've noticed that in the minimal solution, the "up" guide will have no