A greedy algorithm about assigning time to tasks to Maximize the total time

Question

I'm given a number of tasks, each of them has a start time and an end time. I should arrange my day to do them.

Requirements are:

1. Can't do more than one tasks at any time.
2. Can't divide tasks
3. Maximize the total working time

My solution to this is:

1. Rank all tasks by their number of overlaps with all others from the least to most.
2. Select the tasks from the left to right in the above ranked list to do. Make sure that any tasks to choose don't have overlaps with tasks that have been chosen.
3. Calculate the time.

Is this correct? I can't prove it. Does anyone have better idea?

Answer 1

The Activity Selection problem maximises the total number of tasks using a greedy algorithm.

However, your problem is slightly different as you wish to maximise the total time.

You can solve this by solving the shortest path problem in a graph where you have a node for each task.

Make edges from task A to task B if A finishes before B, and set the weight on the edge to the amount of time between the end of A and the start of B.

Make an extra start node that connects to all tasks (with weight equal to the start time of the task), and an extra end node that all tasks connect to (with weight equal to the time between the end of the task and the end of the day).

Note that the weight on each edge corresponds to the amount of time you waste not working if you use that edge.

Computing the shortest path on this graph (e.g. with Dijkstra's algorithm) will tell you the tasks to do with minimum wasted time - which is the same as maximising the work time.

Example

In this graph the shortest path is Start->A->C->End with weight 3, corresponding to doing job A followed by job C, and only wasting 3 hours not working.