#### Overview of this book

C++ is a mature multi-paradigm programming language that enables you to write high-level code with a high degree of control over the hardware. Today, significant parts of software infrastructure, including databases, browsers, multimedia frameworks, and GUI toolkits, are written in C++. This book starts by introducing C++ data structures and how to store data using linked lists, arrays, stacks, and queues. In later chapters, the book explains the basic algorithm design paradigms, such as the greedy approach and the divide-and-conquer approach, which are used to solve a large variety of computational problems. Finally, you will learn the advanced technique of dynamic programming to develop optimized implementations of several algorithms discussed in the book. By the end of this book, you will have learned how to implement standard data structures and algorithms in efficient and scalable C++ 14 code.
Free Chapter
1. Lists, Stacks, and Queues
2. Trees, Heaps, and Graphs
3. Hash Tables and Bloom Filters
4. Divide and Conquer
5. Greedy Algorithms
6. Graph Algorithms I
7. Graph Algorithms II
8. Dynamic Programming I
9. Dynamic Programming II

## 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...