## 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, *p**i*, the amount of time of *a**i* 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 *A**i* shows the service time and *W**i* shows...