Блог пользователя serialcomder

Автор serialcomder, история, 12 месяцев назад, По-английски

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
  • Проголосовать: не нравится

»
12 месяцев назад, # |
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.

»
12 месяцев назад, # |
  Проголосовать: нравится 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?

  • »
    »
    12 месяцев назад, # ^ |
      Проголосовать: нравится 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$$$.

»
12 месяцев назад, # |
  Проголосовать: нравится 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<i$$$ such that:
    • $$$dp[i]\neq-1$$$
    • $$$b[j]_r<b[i]_l$$$ ($$$b[j]$$$ does not intersect with $$$b[i]$$$)
    • $$$\max_{k:a[k]_l\leq b[j]_r}(a[k]_r)<b[i]_l$$$ (all the intervals in $$$S\setminus T$$$ already overlapping with one interval in $$$T$$$ should not intersect with $$$b[i]$$$)
    • $$$\min_{k:b[j]_r<a[k]_l}(a[k]_r)\geq b[i]_l$$$ (intervals between should all intersect with $$$b[i]$$$)
  • $$$dp[i]=-1$$$ otherwise.

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)$$$.