Lecture Rooms
InterviewTime limit2sMemory limit128 MB
Given N lecture intervals, compute the minimum number of rooms needed so no room hosts overlapping lectures, treating touching endpoints as non-overlapping.
Problem
There are N lectures. For each lecture, its start time and end time are known. Assign all lectures using as few rooms as possible.
A room cannot host two or more lectures at the same time. However, if one lecture ends exactly when another lecture starts, those two lectures may use the same room.
Print the minimum number of lecture rooms needed for all lectures.
Input
The first line contains the number of lectures N (1 <= N <= 100,000).
Each of the next N lines contains three integers in the form lecture number start time end time. Lecture numbers are from 1 to N. They may appear in any order in the input, but each number appears exactly once.
Start times and end times are integers between 0 and 1,000,000,000 inclusive, and each start time is less than its end time.
Output
Print one integer: the minimum number of lecture rooms needed.