rumike's blog

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

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

Can it be found in O(n) ?

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

»
3 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
»
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