CODEWITHSUNDEEP
algorithmdynamic-programmingintervalsgraph-coloring
German
German

Reputation: 139

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

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.

Upvotes: 4

Views: 302

Answers (4)

piotrekg2
piotrekg2

Reputation: 1257

Your problem is equivalent to finding the greatest number of intersecting intervals which can be done in O(nlogn).

Proof: Let's say that for a set of intervals S, k is the greatest number of intersecting intervals from S. Clearly we must use at least k numbers for a valid assignment. Now we need to show that k is sufficient. Lets iterate over the intervals from S in ascending order. Each time we open a new interval we choose a number from the set of unused numbers, and each time we close an interval we put the number back to that set. Clearly a set of k numbers is sufficient for that to work.

The c++ code for that:

bool canAssign(const std::vector<std::pair<int, int>> &intervals, int k)
{
    const int left = 0, right = 1;

    std::vector<std::pair<int, int>> ends;
    for (const auto &interval: intervals)
    {
        ends.emplace_back(interval.first, left);
        ends.emplace_back(interval.second, right);
    }

    std::sort(ends.begin(), ends.end());

    int maxStack = 0, stack = 0;
    for (const auto &end: ends)
    {
        if (end.second == left)
            ++stack;
        else
            --stack;

        maxStack = std::max(maxStack, stack);
    } 

    return maxStack <= k;
}

Upvotes: 0

user2357112
user2357112

Reputation: 282026

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.

Upvotes: 4

Codor
Codor

Reputation: 17605

Although no proof is given, the Wikipedia article on interval graphs mentions a result stating that considering the intervals in non-decreasing order of the left bound and greedily assigning the lowest possible color yields an optimal result.

Apparently, a more detailed discussion can be found in the following textbook.

Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03293-7.

Note that according to the Wikipedia article on graph coloring, the chromatic number for interval graphs is exactly the clique number.

Upvotes: 2

orlp
orlp

Reputation: 117926

This is solvable by a simple greedy algorithm and a two stacks: one of intervals/integer pairs (initially empty), and one of integers (initially filled with 0 to k).

Order the intervals by start time and iterate over them. For every interval, first iterate over the stack of pairs and pop every interval with an end time that comes before the current intervals' start time. When popping intervals push the associated integer back into the stack of integers. Afterwards, pop one integer of the integer stack and push it with the current event on the pair stack.

If at any point the integer stack runs out, the problem has no solution. The solution is the pairs of intervals/integers as you pushed them onto the stack.

An alternative solution that has no maximum k is also easy: if the stack of integers is empty you increment k and use that instead.

If you use a priority queue by end time to store the interval/integer pairs, this algorithm should be O(n log n) in the worst case.

Upvotes: 2

Related Questions