1

How to find the interval with max number of intersections? Like if (1,3),(2,9),(4,7),(5,8), output should be (2,9).

I believe one common approach is to create an array = {(a1,start),(b1,end),(a2,start),(b2,end),...,(an,start),(bn,end)} (the first coordinate is a number and the second coordinate is a label). Sort the array according to lexicographic order where start < end (the first coordinate is a number). Initialize count=0 (count will mark the current number of overlapping intervals). Increase the count when sees a start coordinate and decrease the count when sees an end coordinate.

What I don't understand when we create the array, we are essentially separating the start time and end time from each interval. So each start time and end time will lose their identify of which interval they belongs to. When we walk through the array, it would not make sense if we just increment/decrement the count without knowing each coordinate corresponds to which interval. If we use a hashmap and map each coordinate to their interval, there might be issues with duplicate start times and end times.

How should we solve this issue? Thanks.

Matt
  • 20,108
  • 1
  • 57
  • 70
user3216886
  • 421
  • 1
  • 8
  • 15
  • 1
    Get all numbers, sort them, for each interval count the numbers between the ends (keeping in mind that each other interval should be counted only once). – sashkello Jan 23 '14 at 00:47
  • But it seems like there should be a linear time algorithm. By the way, markdown at the last part of your second paragraph. – Teepeemm Jan 23 '14 at 00:48
  • Why do you store only labels of start and end? Store links to the intervals that point belongs to and you'll know to what intreval every point belongs. – Mikhail Melnik Jan 24 '14 at 13:21
  • possible duplicate of [Given a set of intervals, find the interval which has the maximum number of intersections](http://stackoverflow.com/questions/21966886/given-a-set-of-intervals-find-the-interval-which-has-the-maximum-number-of-inte) – itsadok Jul 17 '14 at 03:07

0 Answers0