Intervals & Overlap Scheduling
Data StructuresManaging overlapping timelines, meeting rooms, and range merges
41 problems·3 Easy·27 Medium·11 Hard
Pattern Study Guide & Cheat Sheet▼
Sort ranges by start (or end) time so overlapping relationships can be resolved linearly by comparing adjacent pairs.
Core Invariant: Once sorted by start time (`start_i <= start_j`), interval J overlaps with interval I if and only if `start_j <= end_i`. When overlapping, merged end is `max(end_i, end_j)`.
Recognize it (Keywords & Signals)
- Merge overlapping intervals
- Insert interval into sorted non-overlapping list
- Non-overlapping intervals (erase minimum overlaps)
- Meeting rooms (minimum conference rooms needed / can attend all)
When NOT to use
Intervals cannot be sorted or endpoints are infinite/continuous without discrete ordering.
How to solve (Step-by-step)
- 1.Sort intervals by start time: `intervals.sort(key=lambda x: x[0])`.
- 2.Initialize `merged = [intervals[0]]`.
- 3.Iterate through subsequent intervals `[curr_start, curr_end]`.
- 4.If `curr_start <= merged[-1][1]`: overlap exists! Update `merged[-1][1] = max(merged[-1][1], curr_end)`.
- 5.Else: no overlap. Append `[curr_start, curr_end]` to `merged`.
- 6.Return `merged`.
Watch for (Interview Traps)
- Touching endpoints edge case: verify if `[1, 2]` and `[2, 3]` overlap (`start <= last_end` vs `start < last_end`)
- Forgetting `max(last_end, end)`: the previous interval might already be longer than current
- Meeting Rooms II: sorting only by start time without tracking end times with a heap
Merge Overlapping Intervals
def merge_intervals(intervals: list[list[int]]) -> list[list[int]]:
if not intervals:
return []
# Sort primarily by start time
intervals.sort(key=lambda x: x[0])
merged = [intervals[0]]
for start, end in intervals[1:]:
last_end = merged[-1][1]
if start <= last_end:
# Overlapping intervals: merge by taking the max end
merged[-1][1] = max(last_end, end)
else:
# Non-overlapping: append as separate interval
merged.append([start, end])
return merged- Cost
- O(n log n) dominated by initial sort · O(n) for output list (Linear O(n) pass after the O(n log n) sort.)
Canonical problems
#56 Merge Intervals: Standard sort by start time and extend ends
#57 Insert Interval: Add before overlap, merge during overlap, append after overlap
#435 Non-overlapping Intervals: Greedy: sort by end time to keep intervals that finish earliest
#253 Meeting Rooms II: Min-heap of end times tracks currently occupied rooms
⌘K
Medium·8 companies·Max freq 100%·Acc 61.7%
LivspaceZohoTikTok+5
Medium·7 companies·Max freq 100%·Acc 64.0%
razorpayGrammarlyJPMorgan Chase+4
Medium·7 companies·Max freq 88%·Acc 63.6%
AdobeWalmart LabsIBM+4
Hard·6 companies·Max freq 63%·Acc 59.9%
General MotorsMetaGoogle+3
Hard·5 companies·Max freq 88%·Acc 44.9%
SoFiLinkedInOracle+2
Hard·5 companies·Max freq 60%·Acc 0.5%
NeetCode 150NeetCode 150Google+2
Easy·5 companies·Max freq 38%·Acc 54.6%
MicrosofttcsGoogle+2
Hard·3 companies·Max freq 100%·Acc 52.2%
DirectiMedia.netMedia.net
Medium·3 companies·Max freq 82%·Acc 61.0%
SprinklrAmazonGoogle
Hard·2 companies·Max freq 95%·Acc 31.8%
SprinklrAmazon
Medium·2 companies·Max freq 50%·Acc 44.4%
AgodaSalesforce
Medium·1 companies·Max freq 89%·Acc 0.4%
American Express
Medium·1 companies·Max freq 75%·Acc 50.1%
DE Shaw
Medium·1 companies·Max freq 25%·Acc 46.1%
Amazon
Medium·1 companies·Max freq 25%·Acc 36.9%
Google
Medium·1 companies·Max freq 25%·Acc 49.1%
Google
# | Problem | Difficulty | Top Companies↓ | Frequency | Acceptance | |
|---|---|---|---|---|---|---|
| #56 | Merge Intervals ArraySortingQuicksort | Medium | 100% | 52.3% | ||
| #253 | Meeting Rooms II ArrayTwo PointersGreedySortingHeap (Priority Queue)Prefix Sum | Medium | 100% | 52.7% | ||
| #435 | Non-overlapping Intervals ArrayDynamic ProgrammingGreedySorting | Medium | 88% | 57.4% | ||
| #57 | Insert Interval Array | Medium | 75% | 45.5% | ||
| #986 | Interval List Intersections ArrayTwo PointersSweep Line | Medium | 100% | 73.1% | ||
| #1094 | Car Pooling ArraySortingHeap (Priority Queue)SimulationPrefix Sum | Medium | 89% | 56.4% | ||
| #759 | Employee Free Time ArraySweep LineSortingHeap (Priority Queue) | Hard | 75% | 73.0% | ||
| #729 | My Calendar I ArrayBinary SearchDesignSegment TreeOrdered Set | Medium | 75% | 58.3% | ||
| #2402 | Meeting Rooms III ArrayHash TableSortingHeap (Priority Queue)Simulation | Hard | 63% | 51.4% | ||
| #252 | Meeting Rooms ArraySortingQuicksort | Easy | 60% | 59.5% | ||
| #452 | Minimum Number of Arrows to Burst Balloons ArrayGreedySorting | Medium | 100% | 61.7% | ||
| #2054 | Medium | 100% | 64.0% | |||
| #2406 | Divide Intervals Into Minimum Number of Groups ArrayTwo PointersGreedySortingHeap (Priority Queue)Prefix Sum | Medium | 88% | 63.6% | ||
| #689 | Maximum Sum of 3 Non-Overlapping Subarrays ArrayDynamic ProgrammingSliding WindowPrefix Sum | Hard | 63% | 59.9% | ||
| #1288 | Remove Covered Intervals ArraySorting | Medium | 61% | 60.0% | ||
| #495 | Teemo Attacking ArraySimulation | Easy | 100% | 57.9% | ||
| #2472 | Maximum Number of Non-overlapping Palindrome Substrings Two PointersStringDynamic ProgrammingGreedy | Hard | 88% | 44.9% | ||
| #1851 | Minimum Interval to Include Each Query IntervalsArrayBinary SearchSweep LineSortingHeap (Priority Queue) | Hard | 60% | 0.5% | ||
| #1523 | Easy | 38% | 54.6% | |||
| #1024 | Video Stitching ArrayDynamic ProgrammingGreedy | Medium | 88% | 52.8% | ||
| #2276 | Count Integers in Intervals DesignSegment TreeOrdered Set | Hard | 63% | 36.1% | ||
| #436 | Find Right Interval ArrayBinary SearchSorting | Medium | 25% | 56.1% | ||
| #2479 | Hard | 100% | 52.2% | |||
| #1031 | Maximum Sum of Two Non-Overlapping Subarrays ArrayDynamic ProgrammingSliding Window | Medium | 82% | 61.0% | ||
| #1124 | Longest Well-Performing Interval ArrayHash TableStackMonotonic StackPrefix Sum | Medium | 75% | 37.9% | ||
| #731 | My Calendar II ArrayBinary SearchDesignSegment TreePrefix SumOrdered Set | Medium | 30% | 63.3% | ||
| #2121 | Intervals Between Identical Elements ArrayHash TablePrefix Sum | Medium | 100% | 48.1% | ||
| #3414 | Maximum Score of Non-overlapping Intervals ArrayBinary SearchDynamic ProgrammingSorting | Hard | 95% | 31.8% | ||
| #3893 | Medium | 50% | 44.4% | |||
| #497 | Random Point in Non-overlapping Rectangles ArrayMathBinary SearchReservoir SamplingPrefix SumOrdered SetRandomized | Medium | 28% | 40.1% | ||
| #352 | Data Stream as Disjoint Intervals Hash TableBinary SearchUnion-FindDesignData StreamOrdered Set | Hard | 13% | 60.3% | ||
| #915 | Medium | 13% | 49.5% | |||
| #4016 | Medium | 89% | 0.4% | |||
| #3323 | Minimize Connected Groups by Inserting Interval ArrayBinary SearchSliding WindowSorting | Medium | 75% | 50.1% | ||
| #1520 | Maximum Number of Non-Overlapping Substrings Hash TableStringGreedySorting | Hard | 25% | 43.2% | ||
| #1621 | Number of Sets of K Non-Overlapping Line Segments MathDynamic ProgrammingCombinatoricsPrefix Sum | Medium | 25% | 46.1% | ||
| #1272 | Remove Interval Array | Medium | 25% | 67.3% | ||
| #732 | My Calendar III Binary SearchDesignSegment TreePrefix SumOrdered Set | Hard | 25% | 72.0% | ||
| #1477 | Find Two Non-overlapping Sub-arrays Each With Target Sum ArrayHash TableBinary SearchDynamic ProgrammingSliding Window | Medium | 25% | 36.9% | ||
| #1546 | Maximum Number of Non-Overlapping Subarrays With Sum Equals Target ArrayHash TableGreedyPrefix Sum | Medium | 25% | 49.1% | ||
| #3975 | Filter Occupied Intervals ArraySorting | Medium | 16% | 46.1% |
Showing 41 of 41 problems in Intervals & Overlap SchedulingFiltered: All Companies