Loading...
Loading...
Loading...
On placement day, n interviews are fixed in advance. Interview i starts at minute start and ends at minute end. A room is busy from the start minute up to the end minute, and free again at the end minute. So an interview that ends at minute 30 and one that starts at minute 30 can use the same room.
Two interviews that run at the same time need different rooms. Print the smallest number of rooms that lets every interview happen at its time.
start end for one interview.Example 1
Input
3 0 30 5 10 15 20
Output
2
5 10 and 15 20 can share one room, but both run during 0 30. So 2 rooms are needed.
Example 2
Input
3 1 3 2 4 3 5
Output
2
At minute 3 the first room is free again, so 3 5 can use it. At most two interviews run at once.
Try the problem first. Open one hint at a time.
The answer is the largest number of interviews running at the same moment.
Only the moments when something starts or ends matter. Sort all the start times and, separately, all the end times.
Go through the starts in order with a pointer into the sorted ends. If the earliest unused end is at or before this start, a room has become free and can be reused.
Otherwise you need one more room. Remember that an end equal to a start means the room is free.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor