Find a point where maximum intersection of interval occurs 2 times

Question

I recently went to a competition held offline and they asked this question.

Given n intervals, you have to find a point where there is maximum intersection of intervals.

You can do this 2 times so the sum of intervals should be maximum.

Eg. n=6, (1,3) (2,5) (4,8) (4,8) (3, 7), (6,8)

If we greedily choose 4 first time, we'll get 4 intervals overlap.

4: (2,5) (4,8) (4,8) (3, 7).

Next time we can get only 1 for a total of 5.

either (1,3) or (6,8)

But if we choose 2 in the first instance and 7 in the second instance we'll get 6 as answer.

2: (1,3) (2,5)
7: (4,8) (4,8) (3, 7), (6,8)

Intervals can be in the range [1, 10^9] and 1 <= n <= 10^5

Note: Twice means, You can do that 2 times. You are allowed to choose 2 points such that the sum of intersections in each interval is maximum.Like, you first do that, find a set of ranges which intersect, then remove those and again run on the remaining set. We need to maximise their sum of intersection as such.

Answer 1

Lest visualize the data set you have:

                                  =======    (6,8)
                         =============       (3,7)
                            =============    (4,8) 
                            =============    (4,8) 
                      ==========             (2,5)
                   =======                   (1,3)
                 --|--|--|--|--|--|--|--|--    
                   1  2  3  4  5  6  7  8

 Overlaps:         1  2  3  4  4  4  4  3

It becomes clear that assuming that the interval ends are closed and that all the values are integers there are several point where the maximum amount of intervals overlap: 4, 5, 6 and 7.

Finding them should be very simple:

(pseudocode)

intervals=(
    (6,8),
    (3,7),
    (4,8),
    (4,8),
    (2,5),
    (1,3)
  )

//Find the maximum point because it would be pointless to compute
//up to 10^9. You already know that the line starts at 1, otherwise
//you should find the minimum too.

lastPoint=1

for each interval
  if interval(1)>lastPoint then
    lastPoint=interval(1)

//Check each point

maxPoint=0
matchesAtMax=0

for i=1 to lastPoint
  matches=0
  for each interval
    if interval(0)<=i and interval(1)>=i then
      matches++
  end for
  if matches>=matchesAtMax then
    maxPoint=i
    matchesAtMax=matches
  end if
end for

This will find the last maximum point, stored at maxPoint, which should be 7 with the sample data.

Now, to run it again, we should somehow exclude the intervals that include the maximum point, and check only the remaining intervals. We can do it in the same loop.

(pseudocode)

intervals=(
    (6,8),
    (3,7),
    (4,8),
    (4,8),
    (2,5),
    (1,3)
  )

//Find the maximum point because it would be pointless to compute
//up to 10^9. You already know that the line starts at 1, otherwise
//you should find the minimum too.

lastPoint=1

for each interval
  if interval(1)>lastPoint then
    lastPoint=interval(1)

//Check each point (the greatest first)

remainingIntervals=() //some kind of dynamic array
maxPoint2=0
matchesAtMax2=0 //Lets save both max matches so we can print the final sum

for i=1 to lastPoint
  matches=0
  remainingIntervalsTemp=()
  for each interval
    if interval(0)<=i and interval(1)>=i then
      matches++
    else
      push interval into remainingIntervalsTemp
    end if
  end for
  if matches>=matchesAtMax2 then
    maxPoint2=i
    matchesAtMax2=matches
    remainingIntervals=remainingIntervalsTemp
  end if
end for

//Check the points again using only the remaining intervals
//(Maybe update lastPoint first?)

maxPoint=0
matchesAtMax=0

for i=1 to lastPoint
  matches=0
  allMatchedAreRemaining=true
  for each interval 
    if interval(0)<=i and interval(1)>=i then
      //If this interval is not in the remaining, ignore the point
      if interval is not in remainingIntervals then
            allMatchedAreRemaining=false
            exit for
      end if
      matches++
    end if
  end for
  if allMatchedAreRemaining and matches>=matchesAtMax then
    maxPoint=i
    matchesAtMax=matches
  end if
end for

print maxPoint "+" maxPoint2 "=" (matchesAtMax+matchesAtMax2)

The answer will be stored at maxPoint and maxPoint2. This should print 2+7=6 with the sample data.

It would be wise to optimize it and maybe use functions, it was just an idea, written to be easy to read, not to run perfectly.

Answer 2

the optimal solution can be seen visually. there are 3 best solution 2+6, 2+7 and 3+8.

algorithmically, the best way is to use the brute force method.

start with 1 (see what number remains -> 4,5,6,7,8) check each of the remaining number and remember the score for each pair.

proceed to 2 (see what number remains -> 6,7,8) check each of the remaining number and remember the score for each pair.

continue all the way then get the pairs with the highest score.

note that you don't need to check pairs that was already been checked. e.g. for 4, you don't need to compare with 1,2 or 3 because they have already been checked previously (1+4, 2+4, 3+4).