Finding the maximum number of courses one can taking fewer than $k$ courses at a time

Question

I bumped into this problem (in Spanish), bu Jon Ander Gómez y Alberto Verdejo.

It boils down to:

You are given a list of $n$ online courses ($1 \leq n \leq 10^3)$, each course $i$ defined by the tuple ($s_i$, $e_i$), where $s_i$ is the date the course starts and $e_i$ the day the course ends.

You want to take as many courses as possible, but cannot be enrolled in more than $k=4$ courses at the same time. What is the maximum number of courses you can take?

I am struggling to find the right approach.

Backtracking is out of the question, because $n$ is too large for $O(2^n)$ to be viable. I assume branch-and-bound is out of the question too for the same reason.

I know for $k=1$ (when you can only enroll in one course at a time), a greedy algorithm is the best approach: sorting the courses by end date in ascending order, one would take the first one and from there always take the next course one can enroll once the current one is over. However, it does not seem to work for $k=4$.

Answer 1

Your problem is equivalent to assigning courses to 4 people such that each person can't take more than one course at a time. You can extend the greedy standard earliest-finish-time algorithm to this case.

1. Initialize $e[i] = 0$ for all $i$, indicating the last end time of the courses taken for person $i$.
2. Iterate over the courses in ascending finish time order. For each course $c$ find the largest possible $e[i]$ which is before the start time of $c$. If such an $i$ exists, assign it to person $i$ and set $e[i]$ to the finish time of $c$. If no such $i$ exists we do not take course $c$.

For a proof of optimality see these course notes.