Interval Problems: Merge, Insert, Schedule, and Sweep

Interval problems appear constantly in interviews and real-world systems — scheduling meetings, merging time ranges, finding overlaps in calendar apps, and managing resource allocation. The good news: most interval problems follow a handful of patterns, and once you learn them, new variations become straightforward.

---

1. Interval Representation

An interval is a pair [start, end]. We typically assume:

• start {'<='} end
• Intervals can overlap, touch, or be disjoint
• Most algorithms begin by sorting intervals by start time

# Representation
interval = [1, 5]  # start=1, end=5

# Sorting intervals by start time (primary), end time (secondary)
intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
intervals.sort(key=lambda x: (x[0], x[1]))

---

2. Merge Intervals

Problem: given a list of intervals, merge all overlapping intervals.

This is the fundamental interval operation that many other problems build upon.

def merge_intervals(intervals):
    """
    LeetCode 56: Merge Intervals.

    Time: O(n log n) for sorting
    Space: O(n) for output
    """
    if not intervals:
        return []

    # Sort by start time
    intervals.sort(key=lambda x: x[0])

    merged = [intervals[0]]

    for start, end in intervals[1:]:
        # If current interval overlaps with the last merged one
        if start <= merged[-1][1]:
            # Extend the end of the last merged interval
            merged[-1][1] = max(merged[-1][1], end)
        else:
            # No overlap — add as new interval
            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]] — touching intervals are merged

print(merge_intervals([[1, 4], [0, 4]]))
# [[0, 4]]

When Do Two Intervals Overlap?

def intervals_overlap(a, b):
    """Check if intervals a=[s1,e1] and b=[s2,e2] overlap."""
    return a[0] <= b[1] and b[0] <= a[1]


print(intervals_overlap([1, 3], [2, 5]))  # True
print(intervals_overlap([1, 3], [4, 5]))  # False
print(intervals_overlap([1, 3], [3, 5]))  # True (touching)

---

3. Insert Interval

Problem: given a sorted, non-overlapping list of intervals and a new interval, insert the new interval and merge if necessary.

def insert_interval(intervals, new_interval):
    """
    LeetCode 57: Insert Interval.

    Time: O(n)
    Space: O(n)
    """
    result = []
    i = 0
    n = len(intervals)

    # Add all intervals that come before the new interval
    while i < n and intervals[i][1] < new_interval[0]:
        result.append(intervals[i])
        i += 1

    # Merge overlapping intervals
    while i < n and intervals[i][0] <= new_interval[1]:
        new_interval[0] = min(new_interval[0], intervals[i][0])
        new_interval[1] = max(new_interval[1], intervals[i][1])
        i += 1
    result.append(new_interval)

    # Add all intervals that come after
    while i < n:
        result.append(intervals[i])
        i += 1

    return result


print(insert_interval([[1, 3], [6, 9]], [2, 5]))
# [[1, 5], [6, 9]]

print(insert_interval([[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], [4, 8]))
# [[1, 2], [3, 10], [12, 16]]

print(insert_interval([], [5, 7]))
# [[5, 7]]

---

4. Non-Overlapping Intervals (Interval Scheduling)

Problem: find the minimum number of intervals to remove so that the remaining intervals do not overlap.

This is equivalent to finding the maximum number of non-overlapping intervals (interval scheduling maximisation), then subtracting from the total.

def erase_overlap_intervals(intervals):
    """
    LeetCode 435: Non-overlapping Intervals.

    Greedy: sort by end time, keep intervals that don't overlap.

    Time: O(n log n)
    Space: O(1)
    """
    if not intervals:
        return 0

    # Sort by end time — greedy choice: finish earliest
    intervals.sort(key=lambda x: x[1])

    count = 0  # intervals to remove
    prev_end = intervals[0][1]

    for i in range(1, len(intervals)):
        if intervals[i][0] < prev_end:
            # Overlap — remove this interval (it ends later or same)
            count += 1
        else:
            prev_end = intervals[i][1]

    return count


print(erase_overlap_intervals([[1, 2], [2, 3], [3, 4], [1, 3]]))
# 1 (remove [1,3])

print(erase_overlap_intervals([[1, 2], [1, 2], [1, 2]]))
# 2 (keep one, remove two)

print(erase_overlap_intervals([[1, 2], [2, 3]]))
# 0 (no overlap)

Maximum Non-Overlapping Intervals

def max_non_overlapping(intervals):
    """
    Find the maximum number of non-overlapping intervals.
    Classic greedy interval scheduling.
    """
    if not intervals:
        return 0

    intervals.sort(key=lambda x: x[1])
    count = 1
    prev_end = intervals[0][1]

    for i in range(1, len(intervals)):
        if intervals[i][0] >= prev_end:
            count += 1
            prev_end = intervals[i][1]

    return count


print(max_non_overlapping([[1, 3], [2, 4], [3, 5], [4, 6]]))
# 2 ([1,3] and [4,6])

---

5. Meeting Rooms I

Problem: given a list of meeting time intervals, determine if a person can attend all meetings.

def can_attend_meetings(intervals):
    """
    LeetCode 252: Meeting Rooms.

    Check if any meetings overlap.

    Time: O(n log n)
    Space: O(1)
    """
    intervals.sort(key=lambda x: x[0])

    for i in range(1, len(intervals)):
        if intervals[i][0] < intervals[i - 1][1]:
            return False

    return True


print(can_attend_meetings([[0, 30], [5, 10], [15, 20]]))
# False (0-30 overlaps with 5-10)

print(can_attend_meetings([[7, 10], [2, 4]]))
# True

---

6. Meeting Rooms II

Problem: find the minimum number of meeting rooms required.

Approach 1: Sweep Line (Sort Events)

def min_meeting_rooms(intervals):
    """
    LeetCode 253: Meeting Rooms II.

    Sweep line approach: track start and end events.

    Time: O(n log n)
    Space: O(n)
    """
    events = []
    for start, end in intervals:
        events.append((start, 1))   # meeting starts: +1 room
        events.append((end, -1))    # meeting ends: -1 room

    # Sort by time. On ties, end (-1) comes before start (+1)
    events.sort(key=lambda x: (x[0], x[1]))

    max_rooms = 0
    current_rooms = 0

    for _, delta in events:
        current_rooms += delta
        max_rooms = max(max_rooms, current_rooms)

    return max_rooms


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

print(min_meeting_rooms([[7, 10], [2, 4]]))
# 1

print(min_meeting_rooms([[1, 5], [2, 6], [3, 7], [4, 8]]))
# 4 (all overlap at time 4)

Approach 2: Min-Heap

import heapq

def min_meeting_rooms_heap(intervals):
    """
    Meeting Rooms II using a min-heap.

    The heap tracks the end times of ongoing meetings.
    """
    if not intervals:
        return 0

    intervals.sort(key=lambda x: x[0])

    # Heap contains end times of meetings in progress
    heap = [intervals[0][1]]

    for i in range(1, len(intervals)):
        # If earliest-ending meeting has ended before this one starts
        if heap[0] <= intervals[i][0]:
            heapq.heappop(heap)  # free that room

        heapq.heappush(heap, intervals[i][1])

    return len(heap)


print(min_meeting_rooms_heap([[0, 30], [5, 10], [15, 20]]))
# 2

---

7. Interval List Intersections

Problem: given two lists of sorted, non-overlapping intervals, find their intersection.

def interval_intersection(first_list, second_list):
    """
    LeetCode 986: Interval List Intersections.

    Two pointers, one for each list.

    Time: O(m + n)
    Space: O(1) extra
    """
    result = []
    i = j = 0

    while i < len(first_list) and j < len(second_list):
        # Find the overlap
        lo = max(first_list[i][0], second_list[j][0])
        hi = min(first_list[i][1], second_list[j][1])

        if lo <= hi:
            result.append([lo, hi])

        # Advance the pointer with the smaller end
        if first_list[i][1] < second_list[j][1]:
            i += 1
        else:
            j += 1

    return result


A = [[0, 2], [5, 10], [13, 23], [24, 25]]
B = [[1, 5], [8, 12], [15, 24], [25, 26]]
print(interval_intersection(A, B))
# [[1, 2], [5, 5], [8, 10], [15, 23], [24, 24], [25, 25]]

---

8. The Sweep Line Technique

The sweep line is a general technique for interval problems: instead of thinking about intervals as whole objects, break them into events (start and end), sort the events, and sweep through them.

def sweep_line_template(intervals):
    """
    General sweep line template.

    Converts intervals to events and processes them in order.
    """
    events = []
    for start, end in intervals:
        events.append((start, 'start'))
        events.append((end, 'end'))

    # Sort: by time, then 'end' before 'start' on ties
    # (or reverse, depending on the problem)
    events.sort(key=lambda x: (x[0], 0 if x[1] == 'end' else 1))

    active = 0
    max_active = 0

    for time, event_type in events:
        if event_type == 'start':
            active += 1
        else:
            active -= 1
        max_active = max(max_active, active)

    return max_active

Application: Minimum Arrows to Burst Balloons

def find_min_arrows(points):
    """
    LeetCode 452: Minimum Number of Arrows to Burst Balloons.

    Each balloon is an interval. An arrow at position x bursts
    all balloons where start <= x <= end.

    Greedy: sort by end, shoot at the end of the first un-burst balloon.

    Time: O(n log n)
    """
    if not points:
        return 0

    points.sort(key=lambda x: x[1])
    arrows = 1
    arrow_pos = points[0][1]

    for start, end in points[1:]:
        if start > arrow_pos:
            # This balloon is not burst — need a new arrow
            arrows += 1
            arrow_pos = end

    return arrows


print(find_min_arrows([[10, 16], [2, 8], [1, 6], [7, 12]]))
# 2

print(find_min_arrows([[1, 2], [3, 4], [5, 6], [7, 8]]))
# 4

---

9. Merge Intervals Variants

Employee Free Time

def employee_free_time(schedules):
    """
    LeetCode 759: Employee Free Time.

    Given a list of schedules for each employee (each schedule is a list
    of non-overlapping intervals), find the common free time.

    Time: O(n log n)
    """
    # Flatten all intervals
    all_intervals = []
    for schedule in schedules:
        all_intervals.extend(schedule)

    # Sort by start time
    all_intervals.sort(key=lambda x: x[0])

    # Merge and find gaps
    free_time = []
    prev_end = all_intervals[0][1]

    for start, end in all_intervals[1:]:
        if start > prev_end:
            free_time.append([prev_end, start])
        prev_end = max(prev_end, end)

    return free_time


schedules = [
    [[1, 2], [5, 6]],
    [[1, 3]],
    [[4, 10]],
]
print(employee_free_time(schedules))
# [[3, 4]] — gap between 3 and 4

Remove Covered Intervals

def remove_covered_intervals(intervals):
    """
    LeetCode 1288: Remove Covered Intervals.

    Interval [a, b] is covered by [c, d] if c <= a and b <= d.
    Return the number of remaining intervals after removing covered ones.

    Time: O(n log n)
    """
    # Sort by start ascending, then by end descending
    # This way, if two intervals have the same start,
    # the longer one comes first and "covers" the shorter ones
    intervals.sort(key=lambda x: (x[0], -x[1]))

    count = 0
    max_end = 0

    for _, end in intervals:
        if end > max_end:
            count += 1
            max_end = end
        # else: this interval is covered by a previous one

    return count


print(remove_covered_intervals([[1, 4], [3, 6], [2, 8]]))
# 2 ([1,4] is covered by [2,8]? No. [2,8] covers [3,6]. So remaining: [1,4] and [2,8])

---

10. Interval Scheduling with Weights

When intervals have weights and you want to maximise total weight, greedy alone does not work. You need DP.

import bisect

def weighted_interval_scheduling(intervals):
    """
    Maximum weight subset of non-overlapping intervals.

    Each interval is [start, end, weight].

    Time: O(n log n)
    Space: O(n)
    """
    # Sort by end time
    intervals.sort(key=lambda x: x[1])
    n = len(intervals)

    # Find the latest non-overlapping interval for each interval
    ends = [iv[1] for iv in intervals]

    def find_last_non_overlapping(i):
        """Binary search for the latest interval that ends before intervals[i] starts."""
        target = intervals[i][0]
        lo, hi = 0, i - 1
        result = -1
        while lo <= hi:
            mid = (lo + hi) // 2
            if ends[mid] <= target:
                result = mid
                lo = mid + 1
            else:
                hi = mid - 1
        return result

    # DP: dp[i] = max weight using intervals[0..i]
    dp = [0] * n
    dp[0] = intervals[0][2]

    for i in range(1, n):
        # Option 1: skip interval i
        skip = dp[i - 1]

        # Option 2: take interval i
        take = intervals[i][2]
        j = find_last_non_overlapping(i)
        if j >= 0:
            take += dp[j]

        dp[i] = max(skip, take)

    return dp[n - 1]


intervals = [[1, 3, 5], [2, 5, 6], [4, 6, 5], [6, 7, 4], [5, 8, 11], [7, 9, 2]]
print(weighted_interval_scheduling(intervals))
# 17 ([1,3,5] + [4,6,5] + [7,9,2] = 12? or [1,3,5]+[6,7,4]+... let's compute)

---

11. Summary — Choosing the Right Approach

Problem Type	Technique	Sort By
Merge overlapping	Merge intervals	Start time
Maximum non-overlapping	Greedy	End time
Minimum removals	Greedy (same as above)	End time
Count simultaneous	Sweep line	Event time
Insert into sorted	Linear scan	Already sorted
Find intersections	Two pointers	Both sorted
Maximum weighted	DP + binary search	End time

---

12. Practice Problems

Problem	Platform	Key Technique
Merge Intervals (LC 56)	LeetCode	Basic merge
Insert Interval (LC 57)	LeetCode	Insert + merge
Non-overlapping Intervals (LC 435)	LeetCode	Greedy (sort by end)
Meeting Rooms (LC 252)	LeetCode	Overlap check
Meeting Rooms II (LC 253)	LeetCode	Sweep line / heap
Interval List Intersections (LC 986)	LeetCode	Two pointers
Min Arrows to Burst Balloons (LC 452)	LeetCode	Greedy
Employee Free Time (LC 759)	LeetCode	Merge + gaps
Remove Covered Intervals (LC 1288)	LeetCode	Sort trick
My Calendar I/II/III (LC 729/731/732)	LeetCode	Sweep line

---

Big-O Summary

Algorithm	Time	Space
Merge intervals	O(n log n)	O(n)
Insert interval	O(n)	O(n)
Meeting rooms (overlap)	O(n log n)	O(1)
Meeting rooms II (count)	O(n log n)	O(n)
Interval intersections	O(m + n)	O(1) extra
Interval scheduling (greedy)	O(n log n)	O(1)
Weighted scheduling (DP)	O(n log n)	O(n)

Interval problems reward pattern recognition. The sorting step is almost always the first move, and the choice of sorting by start time vs end time determines which pattern applies. Master merge intervals and sweep line, and you have the tools for nearly every interval problem you will encounter.