# 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?

• @MarzioDeBiasi I don't see how the reduction from the 3-partition problem to this problem could be possible. That problem deals with sums of integers, but my problem doesn't have any summing. Could you give me some directions? – Theemathas Chirananthavat Apr 18 at 9:52
• sorry, I read the question too quickly and didn't notice the "fixed starting time"; there is no direct/quick reduction to 3-PARTITION ! ... I'll think if there is a quick reduction to another problem later. – Marzio De Biasi Apr 18 at 23:04
• @NealYoung: of course, forget my quick fart-like comment (I'll delete it ;-). Lacker's reduction is elegant and correct (so I didn't spend more time on the problem) – Marzio De Biasi Apr 27 at 22:04

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".