Problem 4: Bank Queue

https://open.kattis.com/problems/bank

This is a two-fold greedy problem.

1. To maximize the amount of money deposited, we want to prioritize the people with the most amount of cash to deposit.

2. To make the best use of the time, we want to assign each person to the lastest, unoccupied time they can accept.

For example, if the bank closes in 3 minutes and we currently have 5 clients:

1. Jim, $100, 0

2. Ashley, $50, 1

3. Tyler, $120, 0

4. Beth, $100, 2

5. Maggie, $35, 2

We want to sort them by the amount of money they want to deposit first:

1. Tyler, $120, 0

2. Jim, $100, 0

3. Beth, $100, 2

4. Ashley, $50, 1

5. Maggie, $35, 2

First, we want to serve Tyler first, as he has the most amount of cash. He does not want to wait in a queue any longer, and thus we want to serve him first at minute 1.

Then, we notice that Jim has already run out of patience and left the bank. Sadly, we can't do anything about him. Now Beth is the client with the most money, so we want to assign her to a time slot. Luckily, she is quite patient, and thus we can place her at the lastest unoccupied time she accepts, which is minute 3.

Then, we move on to Ashley. The only time slot left is minute 2, for which she is willing to wait. Thus, we serve her at minute 2.

Note: By putting Beth at minute 3, we are able to serve Ashley. Thus, it's important to assign the client to the lastest unoccupied acceptable time

Finally, since all 3 timeslots have already been taken, Maggie unfortunately cannot deposit her cash today.

The total amount of money deposited is therefore $270.

Implementation Tips

// Pairs are really nice to use here
pair<int, int> p1 = make_pair(100, 1);
pair<int, int> p2 = make_pair(50, 2);
vector<pair<int, int>> vec = {p1, p2};

// C++ natively supports sorting for pairs. 
// by default, it sorts by the first element, 
// then the second.
sort(vec.begin(), vec.end());

// to access the values in a pair, do the following:
cout << p1.first << endl;    // 100
cout << p1.second << endl;   // 1