Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- The Siruseri Welfare Association has organized a Cultural Programme for families in the
- area, to build up community spirit. The Cultural Programme is being held at the Siruseri
- Community Hall. Inside the hall, children perform songs and dances. Outside, local restau-
- rants have set up stalls selling snacks.
- As is typical on such an occasion, members of the audience drift in and out of the hall
- during the programme. An observant office bearer of the Siruseri Welfare Association notes
- down the times at which people enter and leave the hall. At the end of the day, he wonders
- what the maximum size of the audience was during the course of the programme.
- For convenience, he writes down each time as a single integer, the number of minutes
- from the start of the programme. Also, the door of the hall is narrow, so at any time, either
- one person can enter or one person can leave the hall, but not both. Thus, each entry and
- exit time that is noted down is distinct.
- For example, suppose the observations noted down are the following. Each line denotes
- the entry time and exit time of one person. (The identity of the person is not important�the
- same person may enter and leave the hall many times. For instance, in the example below,
- it might well be that the entries and exits recorded at Serial Nos 2 and 5 refer to the same
- person.)
- Serial No Enters at Leaves at
- 1 1 7
- 2 2 4
- 3 6 9
- 4 3 8
- 5 5 10
- In this example, the maximum size of the audience during the programme was 4. This
- was achieved between time 6 and 7.
- Your task is to read the list of entry and exit times and compute the maximum size of
- the audience during the programme.
- Input format
- The first line of input is a single integer, N, the number of entries and exits recorded. This
- is followed by N lines of input. Each of these lines consists of two integers, separated by
- a space, describing one entry and exit. The first integer is the entry time and the second
- integer is the exit time.
- Output format
- A single integer, denoting the maximum size of the audience during the performance.
- 1
- Test data
- For all inputs, 1 N 105. In 70% of the cases, N 5000. The entry and exit times for
- each person are in the range {0, 1, . . . , 107}. All entry and exit times are guaranteed to be
- distinct. For each person, the entry time is guaranteed to be strictly before the exit time.
- Example
- Sample input
- 5
- 1 7
- 2 4
- 6 9
- 3 8
- 5 10
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement