** Next:** Garbage Collection
**Up:** UMD HPC98 Questions
** Previous:** Maximum Repeating Substring

You and your friends Mary and Pete (two social studies students)
are walking around Disneyworld (you've suckered your parents into
taking you all there during the spring break) when all of a sudden
you chance upon this great game booth. Intending to impress your
companions and win over a new love interest, you decide to win a
stuffed animal in the game.

Since you have your notebook computer
with you (don't leave home without it!) a brilliant idea flashes
through your mind. In order to ensure your success and to show
off your new data structures and algorithms skills to these
two liberal-arts people (who, by the way know nothing about either
algorithms or data structures), you decide to come up with
a program that will ASSURE you of winning.

The game gives you a set of intervals on a line, and in order
to win, you must correctly and quickly determine the *density*
of the intervals (i.e., what is the maximum number of intervals
that overlap at any given point on the line).

The vendor in charge of the game agrees to allow you to use your computer
to help you win the game, but agrees only on the conditions that for
each set of intervals, all you can tell the computer is how many intervals
will be in this set, and what the intervals are. The vendor even gives you
a few examples of problems he's used in the past (he is getting
pretty intrigued with this computer idea himself!).

The vendor gives you one last warning before you begin your programming --
the intervals he uses are half-open. This means that the interval
[2,4) includes 2 but not 4. Therefore, if you had two intervals
[2,4) and [4,7), there would be a density of 1 -- no overlap.

Good luck winning the game and your new love!

The input will consist of the number of intervals,
followed by a list of half-open intervals [l,r) giving
the ranges of each interval. All intervals are in integers.
Assume the maximum number of intervals is 100, and the
range of each interval is between 1 and 20.

Output ``Maximum density: " and the maximum line interval density found.

**Input:**

2
2 4
4 7

**Output:**

Maximum density: 1

**Input:**

4
6 8
3 7
1 5
2 4

**Output:**

Maximum density: 3

## Test data used in judging

** Next:** Garbage Collection
**Up:** UMD HPC98 Questions
** Previous:** Maximum Repeating Substring
*Chau-Wen Tseng *

Tue Mar 24 16:22:12 EST 1998