Senior 3 min · March 24, 2026

Interval Scheduling — O(n²) Blowup Led to 30s Timeouts

Q: Is sorting by start time or end time correct for max non-overlapping?

End time. Sorting by start time is a common mistake — it doesn't give optimal results. Example: [(0,100),(1,2),(3,4)] — earliest start is (0,100) which blocks everything; earliest finish (1,2) is much better.

Q: Can I solve the minimum meeting rooms problem without a heap?

Yes: separate starts and ends, sort both arrays, then use a two-pointer scan to count overlapping intervals. That's O(n log n) time and O(n) space, but less intuitive than the heap approach.

Q: What if intervals are already sorted?

For max non-overlapping, if sorted by end time you can do O(n). For meeting rooms, if sorted by start time, the heap logic remains O(n log n) overall because heap operations dominate — but you skip the sort cost.

Q: How do I handle intervals that are inclusive on both ends?

If intervals are [start, end] inclusive, then two intervals [1,4] and [4,5] overlap because 4 is shared. Use <= for overlap detection. If exclusive, use <. The algorithm adjusts accordingly.

Naive O(n²) interval comparison caused 30-second timeouts on imported Outlook calendars.

Naren · Founder

Plain-English first. Then code. Then the interview question.

About

● Production Incident 🔎 Debug Guide

⚡Quick Answer

Interval scheduling finds max non-overlapping meetings using earliest finish time greedy
Minimum meeting rooms: sort starts, track active end times with a min-heap
Merge intervals: sort starts, merge consecutive overlaps in a single pass
All three run O(n log n): the sort dominates
Production trap: assuming sorting by start time works for max intervals — it does not

Plain-English First

You have a list of meetings, each with a start and end time. Two problems: (1) What is the maximum number of non-overlapping meetings you can attend? (2) What is the minimum number of rooms needed to host all meetings simultaneously? Both have elegant greedy solutions.

Interval scheduling appears in every operating system (process time slots), every calendar application (meeting conflict detection), and virtually every resource allocation problem. The three variants — maximise non-overlapping intervals, minimise rooms needed, merge overlapping intervals — are among the most frequently asked algorithmic interview problems at top companies.

All three have elegant O(n log n) greedy solutions, but the correctness argument for each is different. Maximum non-overlapping uses earliest deadline first with an exchange argument. Minimum rooms uses a priority queue sweep. Merge intervals is just careful iteration. Knowing all three and why each works — not just what to code — is what distinguishes thorough preparation.

Problem 1 — Maximum Non-Overlapping Intervals

Greedy insight: always pick the interval that finishes earliest. This leaves maximum room for future intervals.

interval_scheduling.pyPYTHON

def max_non_overlapping(intervals: list[tuple]) -> list[tuple]:
    """
    Returns maximum set of non-overlapping intervals.
    Greedy: sort by end time, always pick earliest finish.
    """
    intervals = sorted(intervals, key=lambda x: x[1])
    selected = []
    last_end = float('-inf')
    for start, end in intervals:
        if start >= last_end:  # no overlap
            selected.append((start, end))
            last_end = end
    return selected

intervals = [(1,4),(3,5),(0,6),(5,7),(3,9),(5,9),(6,10),(8,11),(8,12),(2,14),(12,16)]
result = max_non_overlapping(intervals)
print(f'Max non-overlapping: {len(result)} → {result}')

Output

Max non-overlapping: 4 → [(1, 4), (5, 7), (8, 11), (12, 16)]

Production Insight

A naive implementation that tries all subsets takes O(2^n).

Even O(n^2) pairwise checks break at 10K+ intervals.

Rule: always sort first — O(n log n) greedy is the only safe choice.

Key Takeaway

Sort by end time. Pick first, skip overlaps.

This is the earliest deadline first rule.

If you sort by start time, you get a suboptimal result — that's the #1 mistake.

Choose the Right Algorithm for Maximum Non-Overlapping

IfNeed only count, not the actual intervals?

→

UseUse same greedy — count selected during iteration. No storage needed.

IfIntervals are already sorted by end time?

→

UseO(n) one-pass greedy. Still safe to sort to be sure.

IfIntervals have weights (value per interval)?

→

UseWeighted interval scheduling requires DP O(n log n) — greedy does not work.

Problem 2 — Minimum Meeting Rooms

Use a min-heap tracking end times of active meetings. For each meeting start, if the earliest-ending active meeting has ended, reuse its room.

meeting_rooms.pyPYTHON

import heapq

def min_meeting_rooms(intervals: list[tuple]) -> int:
    if not intervals:
        return 0
    intervals = sorted(intervals, key=lambda x: x[0])
    heap = []  # end times of active meetings
    for start, end in intervals:
        if heap and heap[0] <= start:
            heapq.heapreplace(heap, end)  # reuse room
        else:
            heapq.heappush(heap, end)     # new room needed
    return len(heap)

print(min_meeting_rooms([(0,30),(5,10),(15,20)]))  # 2
print(min_meeting_rooms([(7,10),(2,4)]))             # 1

Output

Production Insight

A queue-based simulation works but leaks memory if not cleaned.

The heap + sweep is the standard pattern.

Watch out for the condition: if heap[0] <= start, you can reuse — not <.

Using '<' forces an extra room for abutting meetings.

Key Takeaway

Sort by start time, use min-heap of end times.

Peak heap size = answer.

This is the classic 'meeting rooms II' (LeetCode 253) pattern.

Problem 3 — Merge Overlapping Intervals

Sort by start time, merge consecutive overlapping intervals.

merge_intervals.pyPYTHON

def merge_intervals(intervals: list[tuple]) -> list[tuple]:
    if not intervals:
        return []
    intervals = sorted(intervals, key=lambda x: x[0])
    merged = [intervals[0]]
    for start, end in intervals[1:]:
        if start <= merged[-1][1]:           # overlapping
            merged[-1] = (merged[-1][0], max(merged[-1][1], end))
        else:
            merged.append((start, end))
    return merged

print(merge_intervals([(1,3),(2,6),(8,10),(15,18)]))  # [(1,6),(8,10),(15,18)]
print(merge_intervals([(1,4),(4,5)]))                  # [(1,5)]

Output

[(1, 6), (8, 10), (15, 18)]

[(1, 5)]

Production Insight

Merging intervals is commonly used in calendar apps to collapse busy slots.

A bug creeps in when intervals are abutting: does [1,4] and [4,5] merge?

The merge condition 'start <= last_end' merges them. If the spec says non-abutting, use '<'.

Always clarify the edge case with your interviewer or product manager.

Key Takeaway

Sort by start time, linear scan.

Merge if next start <= current end.

O(n log n) for sort, O(n) for merge.

Why Earliest Finish Time is Optimal

Claim: picking the interval with the earliest finish time is always in some optimal solution. Proof: suppose optimal starts with interval A instead of E (earliest finish). Replace A with E — since E finishes earlier, this can only improve future compatibility. By induction, greedy is optimal.

Production Insight

The exchange argument is the standard formal proof for greedy interval scheduling.

In practice, engineers often skip the proof and just trust the pattern — that's fine until someone asks 'why' in a design review.

Knowing the proof separates senior from mid-level.

Key Takeaway

Earliest finish time wins because it leaves the most room.

Exchange argument: swap any optimal first choice with the earliest-finisher.

It never makes the solution worse — therefore greedy is optimal.

When Greedy Fails — Weighted Interval Scheduling

The earliest finish time greedy does NOT work when intervals have weights (values). A short, high-value interval might be later than a long, low-value one. For weighted interval scheduling you need dynamic programming: 1. Sort by end time 2. Use DP[i] = max(weight[i] + DP[p(i)], DP[i-1]) where p(i) is the last interval non-overlapping with i. This is O(n log n) with binary search for p(i).

weighted_interval_scheduling.pyPYTHON

def weighted_interval_scheduling(intervals: list[tuple]) -> int:
    # intervals: list of (start, end, weight)
    intervals = sorted(intervals, key=lambda x: x[1])  # sort by end
    n = len(intervals)
    # binary search for last non-overlapping interval
    def last_non_overlap(i):
        lo, hi = 0, i - 1
        while lo <= hi:
            mid = (lo + hi) // 2
            if intervals[mid][1] <= intervals[i][0]:
                lo = mid + 1
            else:
                hi = mid - 1
        return hi
    dp = [0] * n
    dp[0] = intervals[0][2]
    for i in range(1, n):
        include = intervals[i][2]
        j = last_non_overlap(i)
        if j != -1:
            include += dp[j]
        dp[i] = max(include, dp[i-1])
    return dp[-1]

Output

Example: intervals = [(1,4,2), (3,5,5), (0,6,3)] -> returns 5 (choose (3,5) weight 5)

Production Insight

Weighted scheduling appears in profit optimisation for ad slots, resource reservations, etc.

The binary search inside DP is often forgotten in interviews — they implement O(n^2) DP which times out on 10^5 intervals.

Always lead with O(n log n) when weights are involved.

Key Takeaway

Greedy fails when intervals have weights.

Use DP with binary search for O(n log n) weighted scheduling.

The transition: dp[i] = max(include i + dp[p(i)], exclude i).

● Production incidentPOST-MORTEMseverity: high

Naive Interval Scheduling Caused 30-Second Timeouts

Symptom

API endpoint for scheduling recommendations returned HTTP 504 after 30 seconds during peak hours.

Assumption

Developers assumed O(n^2) was acceptable because 'it's just meetings' and never tested with real data volume.

Root cause

The implementation compared every interval against every other interval to find conflicts, resulting in a quadratic blowup when users imported their entire Outlook calendar.

Fix

Replaced the pairwise check with a sweep-line algorithm: sort by start time, track the earliest end time via a min-heap. Runtime dropped from O(n^2) to O(n log n).

Key lesson

Always profile with production-like data volumes before assuming algorithm choice is irrelevant.
Interval scheduling problems often feel small — but calendars grow fast.
When you see an O(n^2) algorithm in an interview solution, that's a red flag.

Production debug guideSymptom -> Action patterns for common bugs3 entries

Symptom · 01

Algorithm returns fewer non-overlapping intervals than expected

→

Fix

Verify the sort key is end time, not start time. Then manually trace the greedy selection on a small custom set — many bugs hide in edge cases like abutting intervals (end == next start).

Symptom · 02

Minimum rooms calculation returns too many rooms

→

Fix

Check that the heap comparison uses '<= start' (allowing reuse when a meeting ends exactly when another starts). If you use '<', you'll overcount rooms by one for abutting meetings.

Symptom · 03

Merged intervals are incorrect for adjacent intervals

→

Fix

Decide whether [1,4] and [4,5] should merge. The problem statement defines 'overlap' inclusively or exclusively. Adjust the merge condition accordingly (<= vs <).

Interval Scheduling Variants Compared

Problem	Sort Key	Data Structure	Time Complexity	Key Insight
Max Non-Overlapping	End time	None	O(n log n)	Earliest finish first
Min Meeting Rooms	Start time	Min-heap (end times)	O(n log n)	Sweep over start times, heap tracks active endings
Merge Intervals	Start time	List (stack)	O(n log n)	Merge when next start <= max end
Weighted Max	End time	DP array + binary search	O(n log n)	Greedy fails — DP with p(i)

Key takeaways

Max non-overlapping

sort by END time (not start time — this is the common mistake), pick greedily. Sorting by start time gives a suboptimal result.

Min meeting rooms

sort by start time, use a min-heap of end times. Size of heap at any point = rooms in use. Peak heap size = answer.

Merge intervals

sort by start time, linear scan — merge if next start <= current end. O(n log n) for sort, O(n) for merge.

Why earliest deadline works

if you could improve by not taking the earliest-finishing interval first, you could swap it in — but swapping never makes things worse. Exchange argument.

LeetCode connection

435 (non-overlapping), 252/253 (meeting rooms), 56 (merge intervals). These four problems cover 80% of interval scheduling interview questions.

Weighted intervals require DP

greedy fails.

Common mistakes to avoid

4 patterns

Sorting by start time for max non-overlapping intervals

Symptom

Algorithm returns a suboptimal set — it picks the earliest start (which may be a long interval that blocks many later intervals).

Fix

Always sort by end time. The greedy that picks earliest finish is provably optimal.

Using '<' instead of '<=' when checking overlap for meeting rooms

Symptom

Minimum room count is off by one for abutting meetings (e.g., [0,5] and [5,10]). The algorithm allocates an extra room because it doesn't consider that the first meeting ends exactly when the second starts.

Fix

Use '<=' when comparing heap[0] <= start to allow reusing the room when the earlier meeting ended exactly at the start of the next.

Merging intervals without clarifying overlap definition

Symptom

Merged intervals either include or exclude abutting pairs inconsistently, causing bugs in downstream calendar displays.

Fix

Explicitly ask: do [1,4] and [4,5] overlap? If yes, condition is 'start <= last_end'. If no, condition is 'start < last_end'.

Applying greedy to weighted interval scheduling

Symptom

Returns incorrect maximum profit because greedy ignores weights.

Fix

Recognise that weighted interval scheduling requires DP. Greedy only works when all intervals have equal weight (or when only count matters).

INTERVIEW PREP · PRACTICE MODE

Interview Questions on This Topic

Q01SENIOR

Why does sorting by end time give the optimal solution for interval sche...

Q02SENIOR

How does the min-heap approach solve the minimum meeting rooms problem?

Q03SENIOR

What is the difference between interval scheduling maximisation and mini...

Q04JUNIOR

How would you find the minimum number of intervals to remove to make the...

Q05SENIOR

What if intervals have weights (profits)? How would you solve it?

Q01 of 05SENIOR

Why does sorting by end time give the optimal solution for interval scheduling?

ANSWER

Because the earliest finishing interval leaves the most room for the rest. Formally, an exchange argument shows that if an optimal solution starts with interval A instead of the earliest-finish interval E, you can replace A with E without reducing the total count — E finishes no later than A, so it can't block more intervals. By induction, there's always an optimal solution that includes the earliest finisher.

FAQ · 4 QUESTIONS

Frequently Asked Questions

Is sorting by start time or end time correct for max non-overlapping?

Can I solve the minimum meeting rooms problem without a heap?

What if intervals are already sorted?

How do I handle intervals that are inclusive on both ends?

🔥

That's Greedy & Backtracking. Mark it forged?

3 min read · try the examples if you haven't