Skip to content

05. Merge 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

1. Merge Intervals (Leetcode:56)

Problem Statement

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

2. Insert Interval (Leetcode:57)

Problem Statement

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

3. Merge Two Sorted Lists (Leetcode:21)

Problem Statement

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

4. Merge Two Binary Trees (Leetcode:617)

Problem Statement

Code and Explaination 

1
Explaination:
This is first approach

1
Explaination:
This is second approach

5. Interval List Intersections (Leetcode:986)

Problem Statement

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

6. Single-Threaded CPU (Leetcode:1834)

Problem Statement

Code and Explaination 

1
Explaination:
This is first approach

1
Explaination:
This is second approach

7. Car Pooling (Leetcode:1094)

Problem Statement

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