Interval List Intersections

Data Structures and Algorithms

Statement

Given two lists of closed intervals intervals1 and intervals2, where each interval has its own start and end time, find the intersections of the two intervals lists.

Constraints

• 0 ≤ intervals1.length(), intervals2.length() ≤ 1000
• 0 ≤ intervals1[i][0] < intervals1[i][1] ≤ 10⁹
• 0 ≤ intervals2[j][0] < intervals2[j][1] ≤ 10⁹
• intervals1[i][1] < intervals1[i + 1][0]
• intervals2[j][1] < intervals2[j + 1][0]

Solution

"""
production algorithm
"""


class Solution:
    def intervals_intersection(self, intervals1, intervals2):
        """
        time complexity O(n + m)
        space complexity O(1)
        """
        index1, index2 = 0, 0
        result = list()

        while index1 < len(intervals1) and index2 < len(intervals2):
            # high of first interval is less than low of second interval
            if intervals1[index1][1] < intervals2[index2][0]:
                index1 = index1 + 1
                continue

            # high of second interval is less than low of first interval
            if intervals2[index2][1] < intervals1[index1][0]:
                index2 = index2 + 1
                continue

            # high of first interval is less than or equal to high of second interval
            if intervals1[index1][1] <= intervals2[index2][1]:
                result.append([max(intervals1[index1][0], intervals2[index2][0]),
                               min(intervals1[index1][1], intervals2[index2][1])])
                index1 = index1 + 1
                continue

            # high of second interval is less than or equal to high of first interval
            result.append([max(intervals1[index1][0], intervals2[index2][0]),
                           min(intervals1[index1][1], intervals2[index2][1])])
            index2 = index2 + 1

        return result

"""
unit tests
"""

from unittest import TestCase
from algorithms.merge_intervals.intervals_intersection.solution import Solution


class SolutionTestCase(TestCase):
    def test_zero_intersections(self):
        # Given
        intervals1 = [[1, 3], [7, 9], [13, 15]]
        intervals2 = [[4, 6], [10, 12], [16, 18]]
        solution = Solution()

        # When
        actual = solution.intervals_intersection(intervals1, intervals2)

        # Then
        expected = []
        self.assertEqual(actual, expected)

    def test_some_intersections(self):
        # Given
        intervals1 = [[1, 3], [5, 10], [11, 12]]
        intervals2 = [[2, 4], [6, 9], [11, 12]]
        solution = Solution()

        # When
        actual = solution.intervals_intersection(intervals1, intervals2)

        # Then
        expected = [[2, 3], [6, 9], [11, 12]]
        self.assertEqual(actual, expected)

Strategy

Merge Intervals.

Explanation

The algorithm iterates the indexes of the first and second intervals lists. If the intervals at the current indexes don’t overlap, then increment the index of the intervals list with the smaller end time. Otherwise, the intervals overlap.

The time that the intervals overlap ranges from the maximum start time of the two intervals at the current indexes to the minimum end time of the two intervals at the current indexes. Append that range to the result list. Then, increment the index of the intervals list with the smaller end time.

After iteration completes, the result list contains the intersections of all intervals.

Time Complexity

Let n and m be the lengths of the first and second intervals lists respectively. At most, every interval of both intervals lists is visited. Therefore, the time complexity of the algorithm is O(n + m).

Space Complexity

The auxiliary space complexity of the algorithm is O(1).

Links

data_structures_algorithms/algorithms/merge_intervals/intervals_intersection at main ·…