Compute minimum number of rooms needed

Q: Compute minimum number of rooms needed

This is a Coding & Algorithms interview question from Google for Software Engineer roles. View the full question and solution on PracHub.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Problem

You are given a list of meetings, each with a start time and end time. A single room can host only one meeting at a time.

Two meetings overlap if one starts before the other ends (treat meetings as half-open intervals [start, end) so a meeting ending at time t does not conflict with another starting at time t).

Task

Return the minimum number of rooms required to host all meetings.

Input

intervals : an array of n pairs [start, end] where 0 <= start <= end .

Output

An integer: the minimum number of rooms needed.

Constraints (typical interview bounds)

1 <= n <= 200000
Times are integers in a reasonable range (e.g., 0 .. 10^9 ).

Example

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

(One room can host [0,30], the other can host [5,10] then [15,20].)