CODEWITHSUNDEEP
algorithmoptimizationintervals
porcupine
porcupine

Reputation: 43

How many intervals are containing an another interval?

There are given N intervals, with start and end points. How many pairs of these intervals exists, such that one interval is containing the another interval?

For example, if the given intervals are:
{2,3},{1,5},{0,10},{2,4}
then we have 5 pairs:
{0,10} contains {2,3}
{0,10} contains {2,4}
{0,10} contains {1,5}
{1,5} contains {2,4}
{1,5} contains {2,3}

We are interested just in the number of such pairs. Can you help me finding at least an O(N log N) solution(the O(N^2) is trivial)?

Note: The intervals are given in a form of {startpoint,endpoint}, where startpoint and endpoint can be up to 10^18.

Thank you in advance!

Upvotes: 1

Views: 861

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65447

Sort by startpoint, count the number of inversions in the list of endpoints using the mergesort-derived O(n log n)-time algorithm.

Upvotes: 1

Related Questions