Given a list of number intervals e.g.:

[
[1,5],
[3,7],
[4,10],
[8,17],
[11,13],
[13,19]
]

Find the number of times n or more intervals overlap and how long the total intervals are. For example, if n=3, there would be two overlaps ([1,5], [3,7], [4,10] and [8,17], [11,13], [13,19]). The first overlap occurs over [4,5] and the second overlap occurs over [13,13] so the total length of overlap is (5-4) (13-13) = 1.

CodePudding user response：

Split each interval into begin and end and sort them; make a decision what to do if intervals touch one another (interval starts exactly when other interval ends). In your case, if positions are equal, we should assume begin < end, (x, begin) < (x, end) for all x.

( 1, begin)
( 3, begin)
( 4, begin)
( 5, end)
( 7, end)
( 8, begin)
(10, end)
(11, begin)
(13, begin) # note, that 'begin' should be first
(13, end)   # note, that 'end' should be last
(17, end)
(19, end)

Then loop over this collection adding 1 for begin and subtract 1 for end to the intersection:

Pseudocode:

int intersections = 0;
int start = -1;

int times = 0;
int totalLength = 0;

foreach ((int at, bool isBegin) in collection) {
  if (isBegin) {
    intersections  = 1;

    if (intersections == n) {
      times  = 1;
      start = at;
    }
  }
  else {
    intersections -= 1;

    if (intersections == n - 1) 
      totalLength  = at - start;
  } 
}

WriteLine($"{times} intervals with {totalLength} length in total");

Time complexity: O(m * log(m)), space complexity: O(m) where m is a number of given intervals