Greedy Algorithm Optimization

Question

Consider a DVR recorder that has the duty to record television programs. Each program has a starting time and ending time. The DVR has the following restrictions:

• It may only record up to two items at once.
• If it chooses to record an item, it must record it from start to end.

Given the the number of television programs and their starting/ending times, what is the maximum number of programs the DVR can record?

For example: Consider 6 programs: They are written in the form:

a b c. a is the program number, b is starting time, and c is ending time

1 0 3

2 6 7

3 3 10

4 1 5

5 2 8

6 1 9

The optimal way to record is have programs 1 and 3 recorded back to back, and programs 2 and 4 recorded back to back. 2 and 4 will be recording alongside 1 and 3. This means the max number of programs is 4.

What is an efficient algorithm to find the max number of programs that can be recorded?

Answer 1

This is a classic example for a greedy algorithm.

You create an array with tuples for each program in the input. Now you sort this array by the end times and start going from the left to the right. If you can take the very next program (you are recording at most one program already), you increment the result counter and remember the end-time. For another program again fill the available slot if possible, if not, you can't record it and can discard it.

This way you will get the maximum number of programs that can be recorded in O(nlogn) time.