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.

Answer 2

edit: My mistake, my greedy algorithm solves for maximizing the number of jobs completed which is different than the maximum job time. I'll leave my answer here in case people are curious though.

There are some decent slides for Greedy Scheduling here: Greedy Scheduling

Basically rather than ranking by the number of overlaps, it's best to rank by the order of finish times. By finish time, I don't mean how long it will take to complete, but when it will complete. With the jobs ranked this way, you iterate through until you find a job with start time >= to the current time and then perform that job. Then you repeat until you have no time left.

edit: So this algorithm is labeled greedy because you are always selecting as your next job the one which has the earliest completion time and valid start time.