| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3947 |
| 2 | ecnerwala | 3654 |
| 3 | jiangly | 3627 |
| 4 | jqdai0815 | 3620 |
| 5 | orzdevinwang | 3612 |
| 6 | Benq | 3586 |
| 7 | Radewoosh | 3582 |
| 8 | Geothermal | 3569 |
| 8 | cnnfls_csy | 3569 |
| 10 | ksun48 | 3474 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | awoo | 163 |
| 2 | maomao90 | 160 |
| 3 | adamant | 156 |
| 4 | atcoder_official | 155 |
| 5 | maroonrk | 154 |
| 6 | -is-this-fft- | 148 |
| 6 | SecondThread | 148 |
| 8 | Petr | 147 |
| 9 | nor | 145 |
| 10 | cry | 144 |
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) ?
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)$$$.
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).
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.
Yes but it will not be O(n^2)?
well what if n is equal to the square of the number of intervals?
Auto comment: topic has been updated by rumike (previous revision, new revision, compare).