DSA Intermediate

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.

📅 March 24, 2026 ⏱ 3 min read 🎯 Intermediate

Where developers are forged. · Structured learning · Free forever.

📍 Part of: Greedy & Backtracking → Topic 12 of 13

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

⚙️ Intermediate — basic DSA knowledge assumed

In this tutorial, you'll learn

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

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.

✦ Plain-English analogy ✦ Real code with output ✦ Interview questions

⚡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

Production Incident

Naive Interval Scheduling Caused 30-Second Timeouts

A booking system used an O(n^2) pairwise comparison algorithm that slowed to a crawl with 10,000+ meetings.

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

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

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

FixReplaced 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 Guide

Symptom -> Action patterns for common bugs

Algorithm returns fewer non-overlapping intervals than expected→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).

Minimum rooms calculation returns too many rooms→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.

Merged intervals are incorrect for adjacent intervals→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 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.py · PYTHON

1234567891011121314151617

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.py · PYTHON

12345678910111213141516

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

2
1

📊 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.py · PYTHON

1234567891011121314

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.py · PYTHON

1234567891011121314151617181920212223

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).

🗂 Interval Scheduling Variants Compared

When to use which approach

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

✕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 Questions on This Topic

QWhy does sorting by end time give the optimal solution for interval scheduling?Mid-levelReveal
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.
QHow does the min-heap approach solve the minimum meeting rooms problem?Mid-levelReveal
We sweep from earliest start to latest. For each meeting, we check if the room (heap) of the earliest-ending active meeting is free (heap[0] <= start). If yes, we reuse that room by replacing its end time with the current meeting's end time. If not, we add a new room. The heap size at any moment is the number of concurrent meetings, and the maximum heap size over the sweep is the answer.
QWhat is the difference between interval scheduling maximisation and minimum room allocation?SeniorReveal
Maximisation finds the largest set of non-overlapping intervals — you skip conflicts, aiming to attend as many as possible. Minimum rooms asks: 'if you must schedule all intervals, how many rooms do you need?' It's an online resource allocation problem using a sweep line and heap. They are dual problems but solved with different greedy strategies.
QHow would you find the minimum number of intervals to remove to make the rest non-overlapping?JuniorReveal
That's equivalent to finding the maximum non-overlapping set (LeetCode 435). The minimum removals = total intervals - max non-overlapping. Use the greedy earliest-finish algorithm to get the max non-overlapping set, then subtract from total count.
QWhat if intervals have weights (profits)? How would you solve it?SeniorReveal
Use dynamic programming. Sort intervals by end time. Let dp[i] = max profit using first i intervals. For interval i, find the last interval j that ends before interval i starts (binary search). Then dp[i] = max(weight[i] + dp[j], dp[i-1]). Complexity O(n log n).

Frequently Asked Questions

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.

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.

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.

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.

🔥

Naren Founder & Author

Developer and founder of TheCodeForge. I built this site because I was tired of tutorials that explain what to type without explaining why it works. Every article here is written to make concepts actually click.

About Naren Get in touch

Forged with 🔥 at TheCodeForge.io — Where Developers Are Forged