Is there a polynomial algorithm to find an assignment of integers to intervals?

Question

I have the following problem: given a list of intervals of time and an integer k, is there an assignment of values <= k to intervals such that no two intervals that overlap have the same value? Is there a polynomial algorithm to solve this problem? I think it could be solved with dynamic programming but I can't come up with a solution.

Answer 1

You have k machines and a bunch of jobs (intervals) coming in, each with a start and end time. Each job will tie up a machine for the duration of its time interval. You want to find out whether you can handle all the jobs.

When a job comes in, it doesn't matter which machine you assign it to, only that there is an unoccupied machine. Similarly, it doesn't matter which machines are occupied, only what jobs are running. A job on machine 1 that'll finish in 2 hours is the same as a job on machine 3 that'll finish in 2 hours; either way, you have a machine occupied for the next two hours.

Your decisions are meaningless. At any time, there is a certain set of jobs running and a number of unoccupied machines. That's all that matters.

---

With this in mind, it's pretty easy to do the job in polynomial time. Just sort the intervals by left endpoint and go through in one pass, greedily assigning each interval any value that fits. How you keep track of which machines are occupied will affect your runtime, but pretty much any tracking method still takes polynomial time.