### rumike's blog

By rumike, history, 5 weeks ago,

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) ?

• -11

 » 5 weeks ago, # |   +1 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)$.
•  » » 5 weeks ago, # ^ |   0 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).
•  » » » 5 weeks ago, # ^ |   +1 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.
•  » » » » 5 weeks ago, # ^ |   0 Ah yes, you're right.
 » 5 weeks ago, # | ← Rev. 2 →   0 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.
•  » » 5 weeks ago, # ^ |   0 Yes but it will not be O(n^2)?
•  » » » 5 weeks ago, # ^ |   0 well what if n is equal to the square of the number of intervals?
•  » » » » 5 weeks ago, # ^ | ← Rev. 3 →   0 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 : SpoilerA \ ( A n B) and not what I was thinking (A u B) / (A n B)So the question comes naturally, does the difference can be done in O(nlogn)
 » 5 weeks ago, # |   0 Auto comment: topic has been updated by rumike (previous revision, new revision, compare).
 » 5 weeks ago, # | ← Rev. 2 →   +1 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: None — $a_l\leq a_r •  » » 5 weeks ago, # ^ | ← Rev. 4 → 0 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 •  » » » 5 weeks ago, # ^ | 0 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_lb_r-a_r+a_l-b_l\$ and since we are dealing with max the wrong difference will never be chosen.
•  » » » » 5 weeks ago, # ^ |   0 Got it, thank you.