Intervals: Ranges and Overlaps · Data Structures & Algorithms

Interval Basics

Strip the wording off any interval problem and the same question is hiding underneath: do these two ranges touch? An interval is a pair [start, end], a meeting from 9 to 11, a process alive from time 3 to time 7. Learn to answer the overlap question cheaply and everything else in this section is a variation on that one skill.

Overlap conditions (assume start <= end). [1, 5] and [3, 7] overlap because B starts before A ends. [1, 5] and [6, 7] don't, because B starts after A ends. In full generality two intervals overlap when A.start <= B.end AND B.start <= A.end. Once you've sorted by start you already know A came first, so that whole condition collapses to a single check: curr.start <= prev.end.

The boundary trap: do [1, 5] and [5, 7] overlap? There's no universal answer. Inclusive boundaries say yes, exclusive say no, and the problem statement is the only authority. When it stays silent, ask before you write a line. Guessing wrong at that shared endpoint is the most common interval bug in interviews, an off-by-one that clears your first couple of test cases and dies on the next one.

O(n log n) Sort. Always sort first.
O(n) Merge. Single pass after sort.
O(n) Insert. Three-phase scan.
O(n log n) Min Rooms. Sort + heap.

Why Sorting Is Everything

Sorting is the first move, every single time. Leave the intervals unsorted and any one of them can overlap any other, which means comparing every pair at O(n²). Sort by start time and the overlapping ones land next to each other, so a single left-to-right pass catches all of them in O(n).

Why does this hold? If intervals are sorted by start time and interval A comes before interval B, then A.start <= B.start. The only question left is whether A's range extends far enough to reach B. If A.end >= B.start, they overlap. If not, nothing after B can overlap with A either, because everything after B starts even later. Once you find a gap, you never look backwards. That one fact drops Merge Intervals from O(n²) brute force to O(n log n).

The Merge Process

Merge Intervals puts sorting to work. Once the list is sorted, an overlap is always the next interval in line.

Input: Unsorted Intervals

[[2,6], [1,3], [15,18], [8,10]] in random order. Any pair could overlap, so without sorting we'd need O(n^2) comparisons.

[2,6]

[1,3]

[15,18]

[8,10]

Unsorted -- overlaps are hidden

Recognizing Interval Problems

Merge overlapping intervals

Sort + extend

Sort by start, merge adjacent overlaps

Insert an interval

Three phases

Before, merge overlaps, after

Find intersections

Two pointers

Advance the pointer that ends first

Can attend all meetings?

Sort + conflict check

Any overlap = conflict

Minimum rooms needed

Heap or sweep line

Track concurrent meetings

The Two Core Patterns

Merge & Insert

Combine overlapping intervals

Sort by start time, then sweep left to right. If current overlaps with previous, extend. Otherwise, start a new interval.

Merge IntervalsInsert IntervalInterval List Intersections

Scheduling

Handle conflicts and resources

Use a heap to track end times of ongoing events, or use sweep line to count events at each moment.

Meeting RoomsMeeting Rooms IINon-overlapping Intervals

Merge Intervals

Given a list of intervals, merge all overlapping intervals. Sort first, then sweep left to right comparing each interval with the last merged one:

python

def merge(intervals):
    if not intervals:
        return []
    
    intervals.sort(key=lambda x: x[0])  # Sort by start time
    merged = [intervals[0]]             # Start with first interval
    
    for current in intervals[1:]:
        last = merged[-1]
        
        if current[0] <= last[1]:       # Overlapping — extend
            last[1] = max(last[1], current[1])
        else:                           # Gap — start new interval
            merged.append(current)
    
    return merged

One comparison decides it. If the current interval starts before or at the point where the previous one ends, they overlap, and you extend by taking the larger end.

Visual:
 
Input:   [---]  [------]    [----]      [----]
         1   3  2      6    8   10      15  18
 
Merged:  [----------]       [----]      [----]
         1          6       8   10      15  18

Insert Interval

Insert a new interval into a sorted list of non-overlapping intervals, merging if necessary. Process the intervals in three phases: before, overlap, and after.

python

def insert(intervals, newInterval):
    result = []
    i, n = 0, len(intervals)
    
    # Phase 1: add intervals that end before newInterval starts
    while i < n and intervals[i][1] < newInterval[0]:
        result.append(intervals[i])     # No overlap possible
        i += 1

Phase 2 merges all overlapping intervals into the new one by expanding its boundaries:

python

    # Phase 2: merge all overlapping intervals
    while i < n and intervals[i][0] <= newInterval[1]:
        newInterval[0] = min(newInterval[0], intervals[i][0])  # Expand left
        newInterval[1] = max(newInterval[1], intervals[i][1])  # Expand right
        i += 1
    result.append(newInterval)          # Add the merged interval

Phase 3 just appends everything that comes after:

python

    # Phase 3: add remaining intervals
    while i < n:
        result.append(intervals[i])     # These start after newInterval ends
        i += 1
    
    return result

The three phases stay separate because the intervals arrive sorted. Each phase owns one non-overlapping region.

Start vs end, don't mix them up. Sort by start when you're merging or scanning intervals in order, which is everything in this lesson. Sort by end when you're greedily picking the largest set of non-conflicting intervals, which the next lesson covers. The reason the choice matters: an interval that ends at time 3 leaves the rest of the timeline wide open, while one running from 1 to 100 blocks nearly every other option, so which endpoint you sort on decides which greedy pick looks best.

Interval Intersection

Find the intersection of two sorted interval lists by walking both with two pointers. For each pair you land on, the intersection is [max(starts), min(ends)].

python

def interval_intersection(firstList, secondList):
    result = []
    i = j = 0
    
    while i < len(firstList) and j < len(secondList):
        a_start, a_end = firstList[i]
        b_start, b_end = secondList[j]
        
        start = max(a_start, b_start)   # Intersection starts at later start
        end = min(a_end, b_end)         # Intersection ends at earlier end

If the intersection is valid, add it. Then advance whichever pointer ends first, since that interval can't intersect with anything else.

python

        if start <= end:                # Valid intersection exists
            result.append([start, end])
        
        if a_end < b_end:              # Advance the one that ends first
            i += 1
        else:
            j += 1
    
    return result

Meeting Rooms

Can a person attend all meetings? Sort by start time and check if any meeting starts before the previous one ends:

python

def can_attend_meetings(intervals):
    intervals.sort(key=lambda x: x[0])   # Sort by start time
    
    for i in range(1, len(intervals)):
        if intervals[i][0] < intervals[i-1][1]:  # Starts before prev ends
            return False                  # Conflict — can't attend both
    
    return True                           # No overlaps found

Any overlap means a conflict. After sorting, you only need to compare consecutive intervals. Non-adjacent ones can't overlap if adjacent ones don't.

Say the sort out loud. Lead with it: 'I'll sort by start time so I can walk the intervals in order and only ever compare adjacent pairs.' Then trace a single merge step by hand before you touch syntax, so your interviewer sees the plan and not just the code.

Meeting Rooms II (Min Rooms)

What's the minimum number of meeting rooms needed? Use a min-heap to track when rooms free up. Sort by start time, then process each meeting:

python

import heapq
def min_meeting_rooms(intervals):
    if not intervals:
        return 0
    
    intervals.sort(key=lambda x: x[0])      # Sort by start time
    rooms = []                               # Min-heap of end times
    heapq.heappush(rooms, intervals[0][1])   # First meeting gets a room

For each subsequent meeting, check if the earliest-ending room is free. If so, reuse it; otherwise, allocate a new room:

python

    for i in range(1, len(intervals)):
        if intervals[i][0] >= rooms[0]:      # Earliest room is free
            heapq.heappop(rooms)             # Reuse that room
        heapq.heappush(rooms, intervals[i][1])  # Assign room
    
    return len(rooms)                        # Rooms still in use = answer

The heap size at any point equals the number of rooms in use. The final heap size is the maximum concurrent meetings.

What This Section Covers

Interval PatternsPattern

Non-overlapping, remove covered, partition

Sort First, Compare Neighbors

Every interval problem opens on the same line: sort by start time so the overlapping intervals sit next to each other. After that, a single left-to-right pass does the real work, whether you're merging, inserting, or checking for a conflict.

The operations are all small once the sort is in place. Merge extends the previous end to the max of both. Insert splits the timeline into three regions: everything before, the overlap you fold in, and everything after. Intersection walks two pointers and advances whichever interval ends first. Minimum rooms keeps a min-heap of end times, and the heap size is your answer.

Key Takeaways

Always sort by start time first
Overlap check: current.start <= previous.end
Merge: extend previous.end = max(ends)
Insert: three phases (before, merge, after)
Min rooms: heap of end times or sweep line

Next: Interval Patterns