Skip to content

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:

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

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

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

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

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

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

  1. 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.
  2. 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]]

  1. Sort the intervals:
    After sorting by the starting time, the intervals are [[1, 3], [2, 6], [8, 10], [15, 18]].
  2. 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.
  3. Result:
    The merged intervals are [[1, 6], [8, 10], [15, 18]].

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 Explaination 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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
Explaination:
This is first approach

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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]
Explaination:
This is second approach

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 Explaination 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
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
Explaination:
This is first approach

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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
Explaination:
This is second approach

Problem 3. Merge Two Sorted Lists (Leetcode:21)

Problem Statement

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Example 1:

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2:

Input: list1 = [], list2 = []
Output: []

Example 3:

Input: list1 = [], list2 = [0]
Output: [0]

Constraints:

The number of nodes in both lists is in the range [0, 50].
-100 <= Node.val <= 100
Both list1 and list2 are sorted in non-decreasing order.

Code and Explaination 

1
2
3
4
5
6
7
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if list1 and list2:
            if list1.val > list2.val:
                list1, list2 = list2, list1
            list1.next = self.mergeTwoLists(list1.next, list2)
        return list1 or list2
Explaination:
This is not merge intervals problem. fix this later

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        # If one of the lists is empty, return the other list directly
        if not list1:
            return list2
        if not list2:
            return list1

        # Initialize the head of the merged list
        if list1.val < list2.val:
            merged_head = list1
            list1 = list1.next
        else:
            merged_head = list2
            list2 = list2.next

        current = merged_head

        # Traverse both lists and merge them
        while list1 and list2:
            if list1.val < list2.val:
                current.next = list1
                list1 = list1.next
            else:
                current.next = list2
                list2 = list2.next
            current = current.next

        # Attach the remaining part of the non-empty list
        if list1:
            current.next = list1
        elif list2:
            current.next = list2

        return merged_head
Explaination:
This is second approach

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if not list1 or not list2:
            return list1 if list1 else list2

        if list1.val < list2.val:
            list1.next = self.mergeTwoLists(list1.next, list2)
            return list1
        else:
            list2.next = self.mergeTwoLists(list1, list2.next)
            return list2
Explaination:
This is Third approach

Problem 4. Merge Two Binary Trees (Leetcode:617)

Problem Statement

You are given two binary trees root1 and root2.

Imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not. You need to merge the two trees into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of the new tree.

Return the merged tree.

Note: The merging process must start from the root nodes of both trees.

Example 1:

Input: root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
Output: [3,4,5,5,4,null,7]

Example 2:

Input: root1 = [1], root2 = [1,2]
Output: [2,2]

Constraints:

The number of nodes in both trees is in the range [0, 2000].
-10^4 <= Node.val <= 10^4

Code and Explaination 

1
Explaination:
This is first approach

1
Explaination:
This is second approach

Problem 5. 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 Explaination 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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
Explaination:
This is first approach

1
Explaination:
This is second approach

Problem 6. 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 i​​​​​​th​​​​ 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 Explaination 

1
Explaination:
This is first approach

1
Explaination:
This is second approach

Problem 7. 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 Explaination 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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
Explaination:
This is first approach

1
Explaination:
This is second approach

Problem 8: 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 Explaination 

1
Explaination:
This is first approach

1
Explaination:
This is second approach

Problem 9: 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 Explaination 

1
Explaination:
This is first approach

1
Explaination:
This is second approach

Problem 10: 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 Explaination 

1
Explaination:
This is first approach

1
Explaination:
This is second approach