Grokking the Coding Interview: Patterns for Coding Questions
Ask Author
Back to course home

0% completed

Vote For New Content
Solution: Intervals Intersection
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Problem Statement

Given two lists of intervals, find the intersection of these two lists. Each list consists of disjoint intervals sorted on their start time.

Example 1:

Input: arr1=[[1, 3], [5, 6], [7, 9]], arr2=[[2, 3], [5, 7]]
Output: [2, 3], [5, 6], [7, 7]
Explanation: The output list contains the common intervals between the two lists.

Example 2:

Input: arr1=[[1, 3], [5, 7], [9, 12]], arr2=[[5, 10]]
Output: [5, 7], [9, 10]
Explanation: The output list contains the common intervals between the two lists.

Constraints:

  • 0 <= arr1.length, arr2.length <= 1000
  • arr1.length + arr2.length >= 1
  • 0 <= start<sub>i</sub> < end<sub>i</sub> <= 10<sup>9</sup>
  • end<sub>i</sub> < start<sub>i+1</sub>
  • 0 <= start<sub>j</sub> < end<sub>j</sub> <= 10<sup>9</sup>
  • end<sub>j</sub> < start<sub>j+1</sub>

Solution

This problem follows the Merge Intervals pattern. As we have discussed under Insert Interval, there are five overlapping possibilities between two intervals ‘a’ and ‘b’. A close observation will tell us that whenever the two intervals overlap, one of the interval’s start time lies within the other interval. This rule can help us identify if any two intervals overlap or not:

Image

Now, if we have found that the two intervals overlap, how can we find the overlapped part?

Again from the above diagram, the overlapping interval will be equal to:

    start = max(a.start, b.start)
    end = min(a.end, b.end)

That is, the highest start time and the lowest end time will be the overlapping interval.

So our algorithm will be to iterate through both the lists together to see if any two intervals overlap. If two intervals overlap, we will insert the overlapped part into a result list and move on to the next interval which is finishing early.

Step-by-Step Algorithm

  1. Initialize Pointers:

    • Create two pointers i and j set to 0. These will track the positions in arr1 and arr2.

  2. Create Result List:

    • Initialize an empty list result to store the intersection intervals.

  3. Iterate Over Both Lists:

    • Use a while loop to iterate as long as both pointers i and j are within the bounds of their respective lists.

  4. Check for Overlap:

    • For intervals arr1[i] and arr2[j], check if they overlap:
      • Condition 1: arr1[i].start >= arr2[j].start and arr1[i].start <= arr2[j].end
      • Condition 2: arr2[j].start >= arr1[i].start and arr2[j].start <= arr1[i].end
    • If either condition is true, it means the intervals overlap.

  5. Calculate Intersection:

    • If the intervals overlap, calculate the intersection interval:
      • start = Math.max(arr1[i].start, arr2[j].start)
      • end = Math.min(arr1[i].end, arr2[j].end)
    • Add this intersection to the result list.

  6. Move Pointer:

    • Move the pointer which has the interval ending first to the next interval:
      • If arr1[i].end < arr2[j].end, increment i.
      • Otherwise, increment j.

  7. Return Result:

    • After the loop completes, return the result list containing all intersections.

Algorithm Walkthrough

Using the input arr1=[[1, 3], [5, 6], [7, 9]] and arr2=[[2, 3], [5, 7]]:

  1. Initial State:

    • i = 0, j = 0
    • arr1[0] = [1, 3]
    • arr2[0] = [2, 3]

  2. First Comparison:

    • Check overlap:
      • arr1[0].start >= arr2[0].start and arr1[0].start <= arr2[0].end => 1 >= 2 and 1 <= 3 (False)
      • arr2[0].start >= arr1[0].start and arr2[0].start <= arr1[0].end => 2 >= 1 and 2 <= 3 (True)
    • Intersection: [2, 3]
    • result = [[2, 3]]
    • Move i to next interval (since arr1[0].end < arr2[0].end is False).

  3. Next State:

    • i = 0, j = 1
    • arr1[0] = [1, 3]
    • arr2[1] = [5, 7]

  4. Second Comparison:

    • Check overlap:
      • arr1[0].start >= arr2[1].start and arr1[0].start <= arr2[1].end => 1 >= 5 and 1 <= 7 (False)
      • arr2[1].start >= arr1[0].start and arr2[1].start <= arr1[0].end => 5 >= 1 and 5 <= 3 (False)
    • No intersection.
    • Move i to next interval (since arr1[0].end < arr2[1].start is True).

  5. Next State:

    • i = 1, j = 1
    • arr1[1] = [5, 6]
    • arr2[1] = [5, 7]

  6. Third Comparison:

    • Check overlap:
      • arr1[1].start >= arr2[1].start and arr1[1].start <= arr2[1].end => 5 >= 5 and 5 <= 7 (True)
      • arr2[1].start >= arr1[1].start and arr2[1].start <= arr1[1].end => 5 >= 5 and 5 <= 6 (True)
    • Intersection: [5, 6]
    • result = [[2, 3], [5, 6]]
    • Move i to next interval (since arr1[1].end < arr2[1].end is True).

  7. Final State:

    • i = 2, j = 1
    • arr1[2] = [7, 9]
    • arr2[1] = [5, 7]

  8. Fourth Comparison:

    • Check overlap:
      • arr1[2].start >= arr2[1].start and arr1[2].start <= arr2[1].end => 7 >= 5 and 7 <= 7 (True)
      • arr2[1].start >= arr1[2].start and arr2[1].start <= arr1[2].end => 5 >= 7 and 5 <= 9 (False)
    • Intersection: [7, 7]
    • result = [[2, 3], [5, 6], [7, 7]]
    • Move j to next interval (since arr2[1].end < arr1[2].end is True).

  9. End:

    • Loop ends as j is out of bounds.
    • Result: [[2, 3], [5, 6], [7, 7]]

Code

Here is what our algorithm will look like:

Python3
Python3
. . . .

Time Complexity

As we are iterating through both the lists once, the time complexity of the above algorithm is O(N + M), where ‘N’ and ‘M’ are the total number of intervals in the input arrays respectively.

Space Complexity

Ignoring the space needed for the result list, the algorithm runs in constant space O(1).

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible