N Meetings in One Room

There is one meeting room. You are given a list of meetings, where each meeting is [start, end]. Only one meeting can occupy the room at a time, and a meeting can start only strictly after the previous one ends (a start time equal to another's end time counts as a clash).

Return the maximum number of meetings the room can host.

Hints

· Stuck? Reveal one nudge at a time.

You want the most non-overlapping meetings — which one should you always pick first?

Sort the meetings by their end time.

Greedily take each meeting that starts strictly after the last one you kept.

Common doubts

The meeting that ends earliest frees the room soonest, leaving the most room for future meetings. Sorting by start can pick a long meeting that blocks several short ones.

The problem treats a meeting starting exactly when another ends as a clash, so only a strictly-later start is compatible.

Yes — an exchange argument shows replacing any optimal schedule's first meeting with the earliest finisher never loses a later meeting, so the greedy matches the optimum.

Interview follow-ups

· What an interviewer asks next.

Then greedy fails; it becomes weighted interval scheduling, solved by sorting by end and DP with binary search for the last compatible meeting.

Sort by start and use a min-heap of end times; a meeting reuses a room whose meeting has ended, otherwise opens a new one (bounded by k).

Fun facts

Activity selection is the canonical greedy proof in algorithms courses — the earliest-finish rule is provably optimal via a clean exchange argument.
The same 'earliest finish' idea schedules jobs on a single machine to maximize throughput.

Asked at

AmazonGoogleMicrosoft

Frequently Sometimes Occasionally

Example 1

Input: meetings = [[1,2],[3,4],[0,6],[5,7],[8,9],[5,9]]
Output: 4
Choose meetings [1,2], [3,4], [5,7], [8,9] — four non-overlapping meetings.

Example 2

Input: meetings = [[10,20],[12,25],[20,30]]
Output: 1
All three overlap pairwise (and [10,20] touches [20,30] at 20), so only one fits.

Constraints

- 1 <= meetings.length <= 10^5 - 0 <= start < end <= 10^9

This is the textbook activity selection problem, and the winning move is almost a slogan: always take the meeting that finishes earliest. Finishing early frees the room soonest, leaving the most time for everything still to come.

Prerequisites

Before you start

· Concepts used directly in the solution.

Sorting by finish time. The single decision that makes the greedy correct.

Interval overlap. Two meetings clash unless one ends strictly before the other starts.

Exchange argument. Swapping in the earliest-finishing meeting never reduces the count.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

The rules

“Can a meeting start exactly when another ends?”

No — the next meeting must start strictly after the previous one ends.

“Is there just one room?”

Yes — so the chosen meetings must be pairwise non-overlapping.

Goal

“Am I maximizing count or total time?”

Count — the number of meetings, regardless of how long each runs.

The ideal opening — say it like this

I'll sort the meetings by their end time.

Then I greedily take each meeting whose start is strictly after the last one I kept.

Picking the earliest finisher each time leaves the most room for the rest — that's the exchange argument.

Understand the problem

Worked example — meetings = [[1,2],[3,4],[0,6],[5,7],[8,9],[5,9]]

sort by end: [1,2] [3,4] [0,6] [5,7] [8,9] [5,9]
[1,2] take (last end = 2)
[3,4] 3 > 2  take (last end = 4)
[0,6] 0 > 4? no  skip
[5,7] 5 > 4  take (last end = 7)
[8,9] 8 > 7  take (last end = 9)
[5,9] 5 > 9? no  skip
answer: 4

Key observations

1Aha

Earliest finish time is the right key

Sorting by end time and taking compatible meetings greedily is optimal. The meeting that ends soonest leaves the room free earliest, maximizing what can follow.

2Aha

Compatibility is a strict inequality

A meeting is compatible with the last kept one iff its start is strictly greater than that meeting's end — back-to-back meetings sharing an instant clash.

3Aha

One pass after sorting

Track only last_end. Sweep the sorted meetings once, incrementing the count and updating last_end whenever you take one.

Brute force vs optimal

	Longest-chain DP	Earliest-finish greedy
Idea	For each meeting, best chain ending at it	Sort by end, take each compatible meeting
Time	O(n^2)	O(n log n)
Space	O(n)	O(1)

The DP considers every earlier meeting as a predecessor; the greedy proves you only ever need the earliest finisher. Full code is in the Approaches selector below.

Summary

Key takeaway

Sort by finish time and greedily take each meeting that starts strictly after the last one you kept. The earliest-finishing meeting frees the room soonest, so the greedy never forecloses a better schedule — O(n log n), O(1) extra space.

sort meetings by end time
last_end = -infinity; count = 0
for [start, end] in meetings:
    if start > last_end:
        count += 1; last_end = end
return count