serialcomder's blog

By serialcomder, history, 17 months ago,

Hey, I came across this problem in a course interview I am not sure how to solve it.

We are given a set of $n$ intervals, let's call it $S$. Now, we have to output any subset $T$ of $S$ such that all the intervals in $T$ are pairwise disjoint (non-overlapping) and all the intervals in $S \smallsetminus T$ should intersect with exactly one interval from $T$.

I am really curious to know what the solution could be.

• +12

 » 17 months ago, # | ← Rev. 2 →   +4 What are the source and the constraint of the problem?I try to think in the direction of "chordal graphs", but no results yet.
•  » » 17 months ago, # ^ |   0 Any polynomial time solution would work. The problem isn't available online, I got it on a hardcopy.
•  » » » 17 months ago, # ^ |   0 Is it guaranteed that this problem is in $P$?
•  » » » » 17 months ago, # ^ |   0 Yes
 » 17 months ago, # |   0 Just a guess, but what about adding into S the biggest interval that won't intersect with any in S, while it is possible?
•  » » 17 months ago, # ^ |   0 I don't think it will work, it might be possible you select an interval which won't intersect with anything in $T$ but selecting it will cause more than one intervals from $T$ to intersect with an interval in $S \smallsetminus T$.
 » 17 months ago, # |   0 Would this work?Let $a$ be the list of intervals sorted by their left border and $b$ be the list of intervals sorted by their right border. Let $dp[i]$ be the index of the previous interval in $T$ (or $i$ if it is the only interval) if $b[i]$ is the last interval after we have considered up to the $i^{th}$ prefix, or $-1$ if no such $T$ exists. $dp[i]=i$ if $b[i]_l\leq b[0]_r$ $dp[i]=j$ if there exists any \$0\leq j