Interval partitioning with restrictions: NP-complete or efficiently solvable? 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?
Here's a reduction from 3SAT. For each of your 3SAT variables $x_0$, imagine there is one event $x_0$ and two rooms called "Room $x_0$ is true" and "Room $x_0$ is false". The event $x_0$ has to be in one of those two rooms. Whichever statement is true, that's the room we don't use. And it is going to take all day. So the only rooms generally available for other events are the rooms named with a true statement.

Now let's say you want to add a condition - $x_0$ OR $x_1$ OR NOT $x_2$. Make that into an event that's just one nanosecond long, at a random time so it doesn't conflict with the other condition-events. And it has to be held in one of "Room $x_0$ is true", "Room $x_1$ is true", or "Room $x_2$ is false".

Now solving your event assignment problem lets you solve an arbitrary 3SAT problem.