rumike's blog

Interval Problem
By rumike, history, 5 hours 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
  • -9
  • Vote: I do not like it

»
4 hours ago, # |
  Vote: I like it 0 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
  • »
    »
    18 minutes 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
»
3 hours 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
  • »
    »
    15 minutes ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      1 minute 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
»
8 minutes 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