patternMinor
Choose non-adjacent numbers from intervals
Viewed 0 times
adjacentnonchoosenumbersintervalsfrom
Problem
Given a list of intervals with integral endpoints, we want to find out if we can choose one integer from each interval so that no two chosen numbers are adjacent. Can we do this in polynomial time?
My attempt is the following greedy strategy: Sort the intervals by the smaller left endpoint, breaking ties by the smaller right endpoint. Then, as long as possible, choose the leftmost feasible number from each interval.
However, this doesn't work: the first interval may be $[5,9]$ and the second interval $[6,6]$. Choosing $5$ from the first interval rules out choosing anything from the second interval. It would be better to choose $6$ from the second interval and $8$ from the first interval.
My attempt is the following greedy strategy: Sort the intervals by the smaller left endpoint, breaking ties by the smaller right endpoint. Then, as long as possible, choose the leftmost feasible number from each interval.
However, this doesn't work: the first interval may be $[5,9]$ and the second interval $[6,6]$. Choosing $5$ from the first interval rules out choosing anything from the second interval. It would be better to choose $6$ from the second interval and $8$ from the first interval.
Solution
This problem can be regarded as a scheduling problem.
Each interval corresponds to a job. For each interval $[L_i,R_i]$, Let $r_i = L_i$ be the release time, $d_i = R_i + 2$ be the deadline, and $p_i = 2$ be the job length. Then, single-machine no-preemption scheduling corresponds to a solution. Scheduling with non-integer start times can be converted to integer start times by taking the floor function, and the schedule remains feasible.
This problem has an $O(n \log n)$-time solution [1].
Each interval corresponds to a job. For each interval $[L_i,R_i]$, Let $r_i = L_i$ be the release time, $d_i = R_i + 2$ be the deadline, and $p_i = 2$ be the job length. Then, single-machine no-preemption scheduling corresponds to a solution. Scheduling with non-integer start times can be converted to integer start times by taking the floor function, and the schedule remains feasible.
This problem has an $O(n \log n)$-time solution [1].
- [1] Garey, Michael R., et al. "Scheduling unit–time tasks with arbitrary release times and deadlines." SIAM Journal on Computing (1981).
Context
StackExchange Computer Science Q#155239, answer score: 3
Revisions (0)
No revisions yet.