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.
What are the source and the constraint of the problem?
I try to think in the direction of "chordal graphs", but no results yet.
Any polynomial time solution would work. The problem isn't available online, I got it on a hardcopy.
Is it guaranteed that this problem is in $$$P$$$?
Yes
Just a guess, but what about adding into S the biggest interval that won't intersect with any in S, while it is possible?
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$$$.
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.
We can maintain a sorted list of indices $$$u$$$ with $$$dp[j]\neq-1$$$. The last 3 conditions are monotonic, so we can binary search over $$$u$$$ to find $$$j$$$.
To get the answer, start from any $$$i$$$ where $$$dp[i]\neq-1$$$ and $$$b[i]_r\geq a[n-1]_l$$$. Total TC is $$$O(n\log n)$$$.