rumike's blog

Interval Problem
By rumike, history, 4 months ago, In English

Given a list of interval, find the maximum difference between two intervals. The difference between two intervals A and B is the number of element that are in A and not in B, or in B and not in A.

UDP : It mean element that are exactly only in one of A and B

Can it be found in O(n) ?

  • Vote: I like it
  • -11
  • Vote: I do not like it

»
4 months ago, # |
  Vote: I like it +1 Vote: I do not like it

I fail to see how you could do that in $$$\mathcal{O}(n)$$$ time since, at best, you would likely need to sort your intervals so as to optimise your search/counting. So, at least $$$\mathcal{O}(n\log_2 n)$$$.

→ Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I have already resolved intervals using scanline with O(n) complexity, that's why I put O(n), but I am okay with O(nlogn).

    → Reply
    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      It only works when the range of interval endpoints are also $$$\mathcal{O}(n)$$$. Otherwise, there needs to be any kind of sorting that takes at least $$$\mathcal{O}(n\log{n})$$$ before you can start scanning.

      → Reply
»
4 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

For any pair of intervals, you can first find the amount of space that is in A and the amount of space that is in B, take the max of those, and subtract off the amount of space that is in both. The max of all pairs should be the answer.

→ Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes but it will not be O(n^2)?

    → Reply
    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      well what if n is equal to the square of the number of intervals?

      → Reply
      • »
        »
        »
        »
        4 months ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        No there are no problems, If it's, I want only to know if there is a better algorithm to do it, as you can see in most intervals where brute force idea is O(n^2), but you can actually have O(nlogn). The thing that lead me to that problem is that I was resolving 1834D - Опрос на уроке, and I had done for it a wrong mathematical representation. Before see editorial, I was thinking that the problem can be represented like the difference of two intervals. But actually it is :

        Spoiler

        So the question comes naturally, does the difference can be done in O(nlogn)

        → Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by rumike (previous revision, new revision, compare).

→ Reply
»
4 months ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

You could probably do $$$O(n\log n)$$$ with max fenwick/segment trees. There are 3 kinds of intersections when you fix the rightmost interval:

  1. None — $$$a_l\leq a_r<b_l\leq b_r$$$ difference is $$$a_r-a_l+1+b_r-b_l+1$$$

  2. Partial — $$$a_l<b_l\leq a_r\leq b_r$$$ difference is $$$b_r-a_r+b_l-a_l$$$

  3. Full — $$$b_l\leq a_l\leq a_r\leq b_r$$$ difference is $$$b_r-a_r+a_l-b_l$$$

You can use scanline for 1, and 2 segment trees keeping $$$-a_r-a_l$$$ and $$$a_l-a_r$$$ for 2 and 3 respectively.

From left-to-right in sorted order by the right borders:

  1. Query the first segment tree $$$[l,r]$$$ and add $$$b_r+b_l$$$ to the result

  2. Query the second segment tree $$$[l,r]$$$ and add $$$b_r-b_l$$$ to the result

  3. Update both segment trees at position $$$r$$$

Note that using the first segment tree for 3 or using the second segment tree for 2 does not matter because we are taking the max of all of them.

→ Reply
  • »
    »
    4 months ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    Thank you so much.

    But I don't understand well the querying of segment trees. For example for partial intersection, It is ok to save - ar — al in segment tree before, and during query on range [ bl , br], how to query only intervals a, for which al≤bl<ar≤br is verified.

    → Reply
    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Note that using the first segment tree for 3 or using the second segment tree for 2 does not matter because we are taking the max of all of them.

      For partial $$$a_l<b_l\leq a_r\leq b_r$$$, notice that $$$b_r-a_r+b_l-a_l>b_r-a_r+a_l-b_l$$$ and since we are dealing with max the wrong difference will never be chosen.

      → Reply