Merge Intervals

Data Structures and Algorithms

Statement

Consider an array of closed intervals intervals, where each interval has a start time and an end time. The array is sorted with respect to the start times of each interval. Merge the overlapping intervals and return a new array that contains only non-overlapping intervals.

Constraints

• 1 ≤ intervals.length() ≤ 10³
• intervals[i].length() = 2
• 0 ≤ intervals[i][0] ≤ intervals[i][1] ≤ 10⁴

Solution

"""
production algorithm
"""


class Solution:
    def merge_intervals(self, intervals):
        """
        time complexity O(n)
        space complexity O(1)
        """
        merged = []
        current = intervals[0]

        for index in range(1, len(intervals)):
            if intervals[index][0] <= current[1]:
                current = [current[0], max(current[1], intervals[index][1])]
            else:
                merged.append(current)
                current = intervals[index]

        merged.append(current)
        return merged

"""
unit tests
"""

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


class SolutionTestCase(TestCase):
    def test_zero_overlapping_intervals(self):
        # Given
        intervals = [[1, 3], [4, 6], [7, 9], [10, 12], [13, 15]]
        solution = Solution()

        # When
        actual = solution.merge_intervals(intervals)

        # Then
        expected = [[1, 3], [4, 6], [7, 9], [10, 12], [13, 15]]
        self.assertEqual(actual, expected)

    def test_some_overlapping_intervals(self):
        # Given
        intervals = [[1, 3], [2, 4], [5, 7], [6, 8], [9, 11], [10, 12]]
        solution = Solution()

        # When
        actual = solution.merge_intervals(intervals)

        # Then
        expected = [[1, 4], [5, 8], [9, 12]]
        self.assertEqual(actual, expected)

    def test_all_overlapping_intervals(self):
        # Given
        intervals = [[1, 3], [2, 4], [3, 5], [4, 6], [5, 7]]
        solution = Solution()

        # When
        actual = solution.merge_intervals(intervals)

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

Strategy

Merge Intervals.

Explanation

The algorithm initializes an empty output array to which merged intervals are appended. The algorithm also initializes a current interval as the first interval of the input array. Then, the algorithm iterates the indexes of the input array from 1 to the length of the input array exclusive.

For each index of iteration, if the start time of the interval at the current index is less than or equal to the end time of the current interval, then the intervals are merged. Since the intervals of the input array are sorted with respect to the start time of intervals, the start time of the current interval is less than or equal to the start time of the interval at the current index, so the start time of the current interval is chosen. However, the maximum end time of the interval at the current index and current interval is chosen, since it’s unknown which is largest.

If the start time of the interval at the current index is greater than the end time of the current interval, then the current interval is appended to the output array, and then the interval at the current index becomes the current interval.

When iteration completes, the current interval is appended to the output array. The result output array is all overlapping intervals merged. The output array is returned.

Time Complexity

The algorithm visits all intervals once. Therefore, the time complexity of the algorithm is O(n), where n is the number of intervals.

Space Complexity

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

Links

data_structures_algorithms/algorithms/merge_intervals/merge_intervals at main ·…