### SRM 679, D2, 250-Pointer (ListeningSongs)

### James S. Plank

Tue Sep 13 22:54:52 EDT 2016

It's best to think about this problem in parts, solving each part before proceeding to the
next part:

### Part 1: An album doesn't have T songs

This case is illustrated in example 6, but it comes from the constraints -- **durations1**
and **durations2** can contain between 1 and 100 elements, and **T** will be between 1 and
100. There is nothing in the constraints that says that **durations1.size()** or
**durations2.size()** is ≥ **T**.
So test for this case first, and return -1 if either vector is too small. Test it on example
six.

### Part 2: You should to listen to the **T** shortest songs on each album

The best way to figure this out is to sort both vectors, and then sum up the first **T**
durations in both vectors.
If that number is too big, return -1. Otherwise, subtract the number from the
total number of seconds (you'll have to multiply **minutes** by 60). That's the
amount of time you have left after listening to **T** songs on each album.

### Part 3: Of the remaining songs, listen to the shortest ones until you run out of time, or
you run out of songs

To do this, create a third vector. I called mine "**FD**" for "final durations." Create
this from the songs in the two vectors that are not in the first **T** songs of either
vector.
Now sort **FD**, and run through it, seeing if you can listen to each song. Return if
you can't listen to a song. If you finish **FD**, you're done -- you can listen to all
of the songs!

In sum, this program tripped up a lot of topcoders, but if you split it into parts, and use
the **sort()** method from the algorithms library, the solution is pretty straightforward.