Problem 2: Frosh Week

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

First, we want to ask the question:

Intuitively, what's the best way to assign the tasks?

Ideally, we first want to try to fit the shortest task into the shortest interval. There are two possible cases:

1. The shortest task takes longer than the shortest interval

   Then we know that no other task can be fitted into this interval. We move on to try the next interval.

2. The shortest task can be done in the interval

   We assign the shortest task to this interval. Now that we can move on to the next task and the next shortest interval.

Why does this work?

Doesn't assigning a short task to a long interval seem wasteful?

key things to consider

1. Each interval can only fit in one task.

2. Finishing longer tasks does not give you more points, so why not do the shorter ones first?

Implementation Details

In this problem, we need to sort both the time intervals as well as the tasks.

#include <algorithm.h>

sort(arr, arr+n);             // sort arr[0] to arr[n-1]
sort(vec.begin(), vec.end()); // sorting a vector