You are given as set of n time intervals {(s1, e1), (s2, e2), ..., (sn, en}). The interval (si, ei) has a start time of si and an ending time of ei.

You can think of each interval indicating that a process is active during that time. You may assume that ei>si. Or you can just think of them as horizontal line segments.

You want to find the maximum overlap among all of the given time intervals. Your algorithm simply determines this maximum value and reports it.

The diagram below illustrates an instance of the problem with 6 time intervals, each represented by horizontal line segments.

For this instance, the algorithm would report 4 as the maximum overlap.

Devise an algorithm solving this problem in O(nn) time.

Discussion/details:

Time intervals are inclusive of their end points. As a result, if one interval ends at exactly the same time another begins, the two intervals are overlapping.

The interval start and end times are given as floating point numbers.

The intervals are given in an arbitrary order

Algorithm Description:

You are not expected to give a C function for this problem, but rather an algorithm description.

What makes a good/correct algorithm description? Like a lot of things, we know it when we see it, but a formal set of rules is not always so easy. Nevertheless, Ill try below:

It should be translatable to an actual implementation by any competent computer scientist.

It does not get bogged down with language specific issues. For example, we would probably represent an interval as a structure in C; including the code for an INTERVAL typedef would not be expected or desired! The person described in (1) knows how to do this already!

It avoids a narrative presentation in favor of a step-by-step description.

You do not need to re-invent known algorithms. If, for example, you want to perform a sort of some kind, you dont have to re-invent merge-sort. You can just say use merge-sort to. The ... part is probably important though! What exactly are you sorting and the sorting criteria are important in an algorithm description.

A diagram is often useful

Often a birds-eye view description of the key concepts in the algorithm before a more detailed description can make a huge difference!

An algorithm description also needs two things along with it:

Some kind of argument of correctness -- why it works. It is up to you to show us that it works; it is not our job to determine if/why it does/does not work. This may be folded into the algorithm description in some cases, but it must be in there somehow.

A runtime analysis. Sometimes this will be trivial, but it must still be in there.