The interval partitioning problem can be solved efficiently using a greedy algorithm. However, adding restrictions on the interval assignment to the problem results in a problem that appears harder. Here's my problem formulation:
- There are $n$ rooms. We want to hold $m$ events in these rooms. These events have fixed (given as input) starting times $s_1,\dots,s_m$ and finishing times $f_1,\dots,f_m$.
- Each event must be held in exactly one room, and two events cannot be held in the same room at the same time.
- Certain events can be held in only certain rooms. This is given as an input as an $n$ by $m$ matrix of booleans.
- We want to figure out whether all events can be held in these rooms.
It seems to me that a greedy algorithm can't solve this. Additionally, since bipartite matching is a special case of this problem (when all events are held at the same time), I have attempted to transform this "interval partitioning with restrictions" problem into a maximum flow problem, with no success. I have also considered trying to prove that this problem is NP-complete, but I don't know where to start.
Could anybody help me either find an efficient algorithm for this or prove that it is NP-complete?