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
| Input 1 | Output 1 |
|---|---|
| Input 2 | Output 2 |
| Input 3 | Output 3 |
| Input 4 | Output 4 |