Meeting Rooms II

Given a list of meeting time intervals, return the minimum number of conference rooms required to hold all of them without any overlap.

Example

Input: [0,30] [5,10] [15,20] Output: 2

Approach

Separate the start times and end times into their own sorted arrays. Walk through both with two pointers: whenever the next meeting starts before the earliest currently-running meeting ends, you need one more room; whenever a meeting ends before the next one starts, you free up a room. The maximum number of rooms in use at any point during this sweep is the answer.

Input format

Line 1: number of meetings R Next R lines: start end

Print the minimum number of rooms required.