Railway Station

Time Limit: 1 sec

 

The Problem

Chittagong railway station is one of the largest train stations. Everyday lot of trains enters the station and departs from here. So platform management is a tough job here. Everyday stuff gets their heart out for managing platforms for the train. They do it manually. But now they want a automated system which will find the minimum number platform needed where arrival and departure time will be given. They need your help.

 

So now you have to write a program. There will be given arrival and departure times of all trains that reach a railway station, find the minimum number of platforms required for the railway station so that no train waits.

 

The Input

There will be multiple test cases. Every case starts with N (1<=N<=200) denoting the number of train arrival. After that there will be N lines to follow, each line contains two integers A(100<=A<=2400) and D(100<=D<=2400) and D must be greater than A.

[Here A is arrival time and D denotes the departure time. Time will be in 24 hour format. For making this easy the time will be given in integer format. As for example 1:06 will be input as 106; 22:30 as 2230 and so on].

 

The Output

For every case you have to print minimum number of platforms needed for those trains in a separate line. Output will be like Case K: P. Here K is the test case number and P is count of platforms needed. For more specifications see the sample input and output.

 

Sample Input

6

900 910

940 1200

950 1120

1100 1130

1500 1800

1800 2000

 

Sample Output

Case 1: 3

 

 

 

Inter University Programming Contest - 2017 [BGC Trust University Bangladesh]

Problem Setter: Parag Paul