04. Overlapping Intervals#

Theory#

Description#

The Merge Intervals technique is commonly used when dealing with a set of intervals, particularly when we need to combine or identify overlapping ranges.

Types of Interval Relationships#

When two intervals, \(a = [a_1, a_2]\) and \(b = [b_1, b_2]\), are compared, they can overlap in various ways. There are six common types of relationships:

Non-overlapping (Separate):
- Condition: \(a_2 < b_1\) or \(b_2 < a_1\)
- Description: The intervals do not overlap and are entirely separate. No merging is needed.
Partial Overlap (b ends after a):
- Condition: \(a_1 \leq b_1 \leq a_2 \leq b_2\)
- Description: The interval \(b\) partially overlaps \(a\), extending beyond it. In this case, \(b\)'s end is after \(a\)'s end.
Complete Overlap (a contains b):
- Condition: \(a_1 \leq b_1 \leq b_2 \leq a_2\)
- Description: The interval \(a\) completely contains \(b\). No merging is needed because \(a\) already encompasses \(b\).
Partial Overlap (a ends after b):
- Condition: \(b_1 \leq a_1 \leq b_2 \leq a_2\)
- Description: The interval \(a\) partially overlaps \(b\), extending beyond it. Here, \(a\)'s end is after \(b\)'s end.
Complete Overlap (b contains a):
- Condition: \(b_1 \leq a_1 \leq a_2 \leq b_2\)
- Description: The interval \(b\) completely contains \(a\). Like the previous case, no merging is needed because \(b\) already includes \(a\).
Identical Intervals:
- Condition: \(a_1 = b_1\) and \(a_2 = b_2\)
- Description: The two intervals are exactly the same. No merging needed since they are already identical.

The General Merge Strategy#

Sorting Intervals
The first step is to sort the intervals by their start points (or first elements). This is crucial because once intervals are ordered, we can easily process them in sequence and determine if any two intervals overlap.
Sorting ensures that we only need to look at adjacent intervals to check for overlap, simplifying the merging process.
Merging Intervals
After sorting, you can iterate through the list of intervals and merge overlapping intervals:
- Start with the first interval.
- For each subsequent interval:
  - If there is no overlap (i.e., the current interval ends before the next one starts), keep both intervals as separate entities.
  - If there is an overlap (i.e., the current interval ends after or exactly at the start of the next interval), merge them by extending the end of the current interval to the maximum end value of both intervals.

Practical Example#

Imagine you have time slots, and you're tasked with finding the combined time frame of various meetings that might overlap.

Given Intervals: [[1, 3], [2, 6], [15, 18], [8, 10]]

Sort the intervals:
After sorting by the starting time, the intervals are [[1, 3], [2, 6], [8, 10], [15, 18]].
Merge the intervals:
- Compare [1, 3] and [2, 6]: Since they overlap (3 > 2), merge them into [1, 6].
- Compare [1, 6] with [8, 10]: No overlap (6 < 8), so keep both intervals.
- Compare [8, 10] with [15, 18]: No overlap (10 < 15), so keep both intervals.
Result:
The merged intervals are [[1, 6], [8, 10], [15, 18]].

Problems at a glance#

LC	Problem
56	Problem 1. Merge Intervals	↗
57	Problem 2. Insert Interval	↗
986	Problem 3. Interval List Intersections	↗
1834	Problem 4. Single-Threaded CPU	↗
1094	Problem 5. Car Pooling	↗
452	Minimum Number of Arrows to Burst Balloons	↗
1353	Maximum Number of Events That Can Be Attended	↗
435	Non-overlapping Intervals	↗

Problems#

Problem 1. Merge Intervals (Leetcode:56)#

Problem Statement

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Example 1:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].

Example 2:

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

Constraints:

1 <= intervals.length <= 10^4 intervals[i].length == 2 0 <= starti <= endi <= 10^4

Code and Explanation

Approach 1 — New merged arrayApproach 2 — In-place compaction

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda x: x[0])
        merged = [intervals[0]]

        for interval in intervals:
            if merged[-1][1] < interval[0]:
                merged.append(interval)
            else:
                merged[-1][1] = max(merged[-1][1], interval[1])

        return merged

Explanation:

Sort intervals by start time so only adjacent pairs can overlap.
Seed merged with the first interval, then scan the rest.
If the current interval starts after the last merged interval ends (merged[-1][1] < interval[0]), append it as a new block.
Otherwise extend the last block's end to max(last_end, current_end).

Time: O(n log n) from sorting · Space: O(n) for the output array

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda x: x[0])
        idx = 0

        for i in range(1, len(intervals)):
            if intervals[idx][1] >= intervals[i][0]:
                intervals[idx][1] = max(intervals[idx][1], intervals[i][1])
            else:
                idx += 1
                intervals[idx] = intervals[i]

        return intervals[:idx + 1]

Explanation:

Sort by start time, same as Approach 1.
Use idx as the write pointer for the last merged interval in the input array.
Overlap with the active block (intervals[idx][1] >= intervals[i][0]) → extend its end in place.
No overlap → advance idx and copy the new interval there.
Return the prefix intervals[:idx + 1] — no extra output array.

Time: O(n log n) · Space: O(1) extra (sort may use O(log n) stack)

Problem 2. Insert Interval (Leetcode:57)#

Problem Statement

You are given an array of non-overlapping intervals intervals where intervals[i] = [starti, endi] represent the start and the end of the ith interval and intervals is sorted in ascending order by starti.
You are also given an interval newInterval = [start, end] that represents the start and end of another interval.

Insert newInterval into intervals such that intervals is still sorted in ascending order by starti and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).

Return intervals after the insertion.

Note that you don't need to modify intervals in-place. You can make a new array and return it.

Example 1:

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

Example 2:

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

Constraints:

0 <= intervals.length <= 10^4
intervals[i].length == 2
0 <= starti <= endi <= 10^5
intervals is sorted by starti in ascending order.
newInterval.length == 2
0 <= start <= end <= 10^5

Code and Explanation

Approach 1 — Three-phase linear scanApproach 2 — Expand newInterval in one pass

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        answer = []
        i, n = 0, len(intervals)

        while i < n and newInterval[0] > intervals[i][0]:
            answer.append(intervals[i])
            i += 1

        if not answer or answer[-1][1] < newInterval[0]:
            answer.append(newInterval)
        else:
            answer[-1][1] = max(answer[-1][1], newInterval[1])

        while i < n:
            if answer[-1][1] < intervals[i][0]:
                answer.append(intervals[i])
            else:
                answer[-1][1] = max(answer[-1][1], intervals[i][1])
            i += 1

        return answer

Explanation:

Before: copy every interval that ends before newInterval starts (here: starts strictly before newInterval[0] while input is sorted).
Insert/merge: append newInterval, or merge it into the last copied interval if they overlap.
After: walk the remaining intervals — append if disjoint, otherwise extend the active block's end.
Mirrors merge-intervals logic on a list that is already sorted.

Time: O(n) · Space: O(n) for the result

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        answer = []
        for i in range(len(intervals)):
            if newInterval[1] < intervals[i][0]:
                answer.append(newInterval)
                return answer + intervals[i:]
            elif intervals[i][1] < newInterval[0]:
                answer.append(intervals[i])
            else:
                newInterval = [min(newInterval[0], intervals[i][0]),
                               max(newInterval[1], intervals[i][1])]

        answer.append(newInterval)
        return answer

Explanation:

Single left-to-right scan over sorted intervals.
Interval entirely before newInterval → copy it to answer.
Interval entirely after newInterval → append expanded newInterval and return with the suffix unchanged.
Overlap → widen newInterval to cover both ranges and continue.
If the loop finishes, every interval overlapped or preceded newInterval — append the final merged block.

Time: O(n) · Space: O(n)

Problem 3. Interval List Intersections (Leetcode:986)#

Problem Statement

You are given two lists of closed intervals, firstList and secondList, where firstList[i] = [starti, endi] and secondList[j] = [startj, endj]. Each list of intervals is pairwise disjoint and in sorted order.

Return the intersection of these two interval lists.

A closed interval [a, b] (with a <= b) denotes the set of real numbers x with a <= x <= b.

The intersection of two closed intervals is a set of real numbers that are either empty or represented as a closed interval. For example, the intersection of [1, 3] and [2, 4] is [2, 3].

Example 1:

Input: firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]]
Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

Example 2:

Input: firstList = [[1,3],[5,9]], secondList = []
Output: []

Constraints:

0 <= firstList.length, secondList.length <= 1000
firstList.length + secondList.length >= 1
0 <= starti < endi <= 109
endi < starti+1
0 <= startj < endj <= 109
endj < startj+1

Code and Explanation

Approach 1 — Two pointers

class Solution:
    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:
        ans, i, j = [], 0, 0

        while i < len(firstList) and j < len(secondList):
            head = max(firstList[i][0], secondList[j][0])
            tail = min(firstList[i][1], secondList[j][1])

            if head <= tail:
                ans.append([head, tail])

            if firstList[i][1] < secondList[j][1]:
                i += 1
            else:
                j += 1

        return ans

Explanation:

Maintain pointers i and j on the two sorted, non-overlapping lists.
For the active pair, overlap (if any) is [max(starts), min(ends)].
Append that segment when head <= tail (non-empty intersection).
Advance the pointer whose interval ends first — that interval cannot intersect any future interval from the other list.
Repeat until one list is exhausted.

Time: O(m + n) · Space: O(1) extra (excluding output)

Problem 4. Single-Threaded CPU (Leetcode:1834)#

Problem Statement

You are given n tasks labeled from 0 to n - 1 represented by a 2D integer array tasks, where tasks[i] = [enqueueTimei, processingTimei] means that the ith task will be available to process at enqueueTimei and will take processingTimei to finish processing.

You have a single-threaded CPU that can process at most one task at a time and will act in the following way:

If the CPU is idle and there are no available tasks to process, the CPU remains idle.
If the CPU is idle and there are available tasks, the CPU will choose the one with the shortest processing time. If multiple tasks have the same shortest processing time, it will choose the task with the smallest index.
Once a task is started, the CPU will process the entire task without stopping.
The CPU can finish a task then start a new one instantly.

Return the order in which the CPU will process the tasks.

Example 1:

Input: tasks = [[1,2],[2,4],[3,2],[4,1]]
Output: [0,2,3,1]
Explanation: The events go as follows:

At time = 1, task 0 is available to process.
Available tasks = {0}.

Also at time = 1, the idle CPU starts processing task 0.
Available tasks = {}.

At time = 2, task 1 is available to process.
Available tasks = {1}.

At time = 3, task 2 is available to process.
Available tasks = {1, 2}.

Also at time = 3, the CPU finishes task 0 and starts processing task 2 as it is the shortest.
Available tasks = {1}.

At time = 4, task 3 is available to process.
Available tasks = {1, 3}.

At time = 5, the CPU finishes task 2 and starts processing task 3 as it is the shortest.
Available tasks = {1}.

At time = 6, the CPU finishes task 3 and starts processing task 1.
Available tasks = {}.

At time = 10, the CPU finishes task 1 and becomes idle

Example 2:

Input: tasks = [[7,10],[7,12],[7,5],[7,4],[7,2]]
Output: [4,3,2,0,1]
Explanation: The events go as follows:

At time = 7, all the tasks become available.
Available tasks = {0,1,2,3,4}.

Also at time = 7, the idle CPU starts processing task 4.
Available tasks = {0,1,2,3}.

At time = 9, the CPU finishes task 4 and starts processing task 3.
Available tasks = {0,1,2}.

At time = 13, the CPU finishes task 3 and starts processing task 2.
Available tasks = {0,1}.

At time = 18, the CPU finishes task 2 and starts processing task 0.
Available tasks = {1}.

At time = 28, the CPU finishes task 0 and starts processing task 1.
Available tasks = {}.

At time = 40, the CPU finishes task 1 and becomes idle.

Constraints:

tasks.length == n
1 <= n <= 10^5
1 <= enqueueTimei, processingTimei <= 10^9

Code and Explanation

Approach 1 — Sort by enqueue time + min-heap

import heapq

class Solution:
    def getOrder(self, tasks: List[List[int]]) -> List[int]:
        indexed = sorted((enqueue, proc, i) for i, (enqueue, proc) in enumerate(tasks))
        heap = []
        res = []
        time = 0
        i = 0
        n = len(indexed)

        while i < n or heap:
            if not heap:
                time = indexed[i][0]

            while i < n and indexed[i][0] <= time:
                heapq.heappush(heap, (indexed[i][1], indexed[i][2]))
                i += 1

            proc, idx = heapq.heappop(heap)
            res.append(idx)
            time += proc

        return res

Explanation:

Sort tasks by enqueueTime while keeping original indices.
Simulate time: when the CPU is idle, jump time to the next task's enqueue time.
Push every task with enqueueTime <= time into a min-heap keyed by (processingTime, index).
Pop the shortest job (ties broken by smallest index), record it, and advance time by its processing duration.
Repeat until all tasks are enqueued and the heap is empty.

Time: O(n log n) · Space: O(n)

Problem 5. Car Pooling (Leetcode:1094)#

Problem Statement

There is a car with capacity empty seats. The vehicle only drives east (i.e., it cannot turn around and drive west).

You are given the integer capacity and an array trips where trips[i] = [numPassengersi, fromi, toi] indicates that the ith trip has numPassengersi passengers and the locations to pick them up and drop them off are fromi and toi respectively. The locations are given as the number of kilometers due east from the car's initial location.

Return true if it is possible to pick up and drop off all passengers for all the given trips, or false otherwise.

Example 1:

Input: trips = [[2,1,5],[3,3,7]], capacity = 4
Output: false

Example 2:

Input: trips = [[2,1,5],[3,3,7]], capacity = 5
Output: true

Constraints:

1 <= trips.length <= 1000
trips[i].length == 3
1 <= numPassengersi <= 100
0 <= fromi < toi <= 1000
1 <= capacity <= 10^5

Code and Explanation

Approach 1 — Sweep line with eventsApproach 2 — Difference array

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        locations = []
        for numPassengers, start, end in trips:
            locations.extend([(start, numPassengers), (end, -numPassengers)])
        locations.sort()

        for _, numPassengers in locations:
            capacity -= numPassengers
            if capacity < 0:
                return False

        return True

Explanation:

Each trip creates two events: +passengers at pickup, -passengers at drop-off.
Sort all events by location (drop-offs before pickups at the same coordinate if needed — here end uses negative delta on a separate event, and sorting (location, delta) works because drop at end happens before pickup at same end when using separate coordinates).
Sweep east: subtract each delta from remaining capacity (pickup reduces free seats).
If capacity goes negative at any point, a trip exceeds the car limit → return false.

Time: O(n log n) · Space: O(n)

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        diff = [0] * 1001
        for passengers, start, end in trips:
            diff[start] += passengers
            diff[end] -= passengers

        onboard = 0
        for change in diff:
            onboard += change
            if onboard > capacity:
                return False

        return True

Explanation:

Locations are bounded (toi <= 1000), so a fixed-size difference array works.
At each pickup start, add passengers; at drop-off end, subtract them.
Prefix-sum the array to get passengers onboard at every mile marker.
If any prefix exceeds capacity, return false.

Time: O(n + L) where L = 1001 · Space: O(L)

Problem 6: Minimum Number of Arrows to Burst Balloons (Leetcode:452)#

Problem Statement

There are some spherical balloons taped onto a flat wall that represents the XY-plane. The balloons are represented as a 2D integer array points where points[i] = [xstart, xend] denotes a balloon whose horizontal diameter stretches between xstart and xend. You do not know the exact y-coordinates of the balloons.

Arrows can be shot up directly vertically (in the positive y-direction) from different points along the x-axis. A balloon with xstart and xend is burst by an arrow shot at x if xstart <= x <= xend. There is no limit to the number of arrows that can be shot. A shot arrow keeps traveling up infinitely, bursting any balloons in its path.

Given the array points, return the minimum number of arrows that must be shot to burst all balloons.

Example 1:

Input: points = [[10,16],[2,8],[1,6],[7,12]]
Output: 2
Explanation: The balloons can be burst by 2 arrows:
- Shoot an arrow at x = 6, bursting the balloons [2,8] and [1,6].
- Shoot an arrow at x = 11, bursting the balloons [10,16] and [7,12].

Example 2:

Input: points = [[1,2],[3,4],[5,6],[7,8]]
Output: 4
Explanation: One arrow needs to be shot for each balloon for a total of 4 arrows.

Example 3:

Input: points = [[1,2],[2,3],[3,4],[4,5]]
Output: 2
Explanation: The balloons can be burst by 2 arrows:
- Shoot an arrow at x = 2, bursting the balloons [1,2] and [2,3].
- Shoot an arrow at x = 4, bursting the balloons [3,4] and [4,5].

Constraints:

1 <= points.length <= 105

points[i].length == 2

-231 <= xstart < xend <= 231 - 1

Code and Explanation

Approach 1 — Greedy by earliest end

class Solution:
    def findMinArrowShots(self, points: List[List[int]]) -> int:
        points.sort(key=lambda x: x[1])
        arrows = 1
        end = points[0][1]

        for i in range(1, len(points)):
            if points[i][0] > end:
                arrows += 1
                end = points[i][1]

        return arrows

Explanation:

Sort balloons by xend (earliest finishing interval first).
Place the first arrow at the end of the first balloon.
For each next balloon: if it starts after the current arrow position (points[i][0] > end), the arrow cannot reach it — shoot a new arrow at this balloon's end.
Touching endpoints count as overlap (xstart <= end), so one arrow still bursts both.
This is the interval-scheduling dual of non-overlapping intervals: maximize balloons per arrow ≡ minimize arrows.

Time: O(n log n) · Space: O(1)

Problem 7: Maximum Number of Events That Can Be Attended (Leetcode:1353)#

Problem Statement

You are given an array of events where events[i] = [startDayi, endDayi]. Every event i starts at startDayiand ends at endDayi.

You can attend an event i at any day d where startDayi <= d <= endDayi. You can only attend one event at any time d.

Return the maximum number of events you can attend.

Example 1:

Input: events = [[1,2],[2,3],[3,4]]
Output: 3
Explanation: You can attend all the three events.
One way to attend them all is as shown.
Attend the first event on day 1.
Attend the second event on day 2.
Attend the third event on day 3.

Example 2:

Input: events= [[1,2],[2,3],[3,4],[1,2]]
Output: 4

Constraints:

1 <= events.length <= 105

events[i].length == 2

1 <= startDayi <= endDayi <= 105

Code and Explanation

Approach 1 — Day sweep + min-heap of end days

import heapq

class Solution:
    def maxEvents(self, events: List[List[int]]) -> int:
        events.sort()
        heap = []
        res = 0
        i = 0
        last_day = max(end for _, end in events)

        for day in range(1, last_day + 1):
            while i < len(events) and events[i][0] <= day:
                heapq.heappush(heap, events[i][1])
                i += 1

            while heap and heap[0] < day:
                heapq.heappop(heap)

            if heap:
                heapq.heappop(heap)
                res += 1

        return res

Explanation:

Sort events by start day.
Sweep each calendar day from 1 to the latest endDay.
Enqueue every event that has started by day d (push its endDay into a min-heap).
Discard events that already ended before today (heap[0] < day).
If the heap is non-empty, attend the event ending soonest (pop min end) — greedy choice frees the day earliest for future events.
Count each attendance.

Time: O(n log n) · Space: O(n)

Problem 8: Non-overlapping Intervals (Leetcode:435)#

Problem Statement

Given an array of intervals intervals where intervals[i] = [starti, endi], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Note that intervals which only touch at a point are non-overlapping. For example, [1, 2] and [2, 3] are non-overlapping.

Example 1:

Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Explanation: [1,3] can be removed and the rest of the intervals are non-overlapping.

Example 2:

Input: intervals = [[1,2],[1,2],[1,2]]
Output: 2
Explanation: You need to remove two [1,2] to make the rest of the intervals non-overlapping.

Example 3:

Input: intervals = [[1,2],[2,3]]
Output: 0
Explanation: You don't need to remove any of the intervals since they're already non-overlapping.

Constraints:

1 <= intervals.length <= 105

intervals[i].length == 2

-5 * 104 <= starti < endi <= 5 * 104

Code and Explanation

Approach 1 — Greedy by earliest end

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x: x[1])
        removed = 0
        prev_end = float('-inf')

        for start, end in intervals:
            if start >= prev_end:
                prev_end = end
            else:
                removed += 1

        return removed

Explanation:

Sort intervals by end time (earliest finish first).
Greedily keep an interval if it starts at or after the last kept end (start >= prev_end) — touching at a point is allowed.
On overlap, skip (remove) the current interval and keep the earlier-ending one already selected.
removed counts intervals we could not keep.

Time: O(n log n) · Space: O(1)