Basic Greedy Algorithms

In this section, we will study two standard problems that can be solved using the greedy approach: shortest-job-first scheduling and the fractional knapsack problem.

Shortest-Job-First Scheduling

Say you are standing in a queue at your bank. It's a busy day and there are N people in the queue, but the bank has only one counter open (it's also a really bad day!). Let's assume that it takes a person, pi, the amount of time of ai to get served at the counter. Since the people in the queue are quite rational, everyone agrees to reorder their places in the queue so that the average waiting time for everyone in the queue is minimized. You are tasked with finding a way of reordering the people in the queue. How would you solve this problem?

Figure 5.2: The original queue

To take this problem apart further, let's look at an example. The preceding figure shows an example of the original queue, where Ai shows the service time and Wi shows...