Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

Insert Interval

Problem Statement
Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary). You may assume that the intervals were initially sorted according to their start times.

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

Example 3

Input: intervals = [], newInterval = [5,7]
Output: [[5,7]]

Example 4

Input: intervals = [[1,5]], newInterval = [2,3]
Output: [[1,5]]

Example 5

Input: intervals = [[1,5]], newInterval = [2,7]
Output: [[1,7]]

Solution

from typing import List


class Solution:
    def insert(self, intervals: List[List[int]], new_interval: List[int]) -> List[List[int]]:
        if len(intervals) == 0:
            return [new_interval]

        result = []

        i = 0
        # Add all intervals that start and end before the new_interval
        for interval in intervals:
            if interval[1] < new_interval[0]:
                result.append(interval)
                i += 1
            else:
                break

        #  Merge all intervals that overlap with the new_interval
        while i < len(intervals):
            if intervals[i][0] <= new_interval[1]:
                new_interval[0] = min(new_interval[0], intervals[i][0])
                new_interval[1] = max(new_interval[1], intervals[i][1])
            else:
                break
            i += 1

        result.append(new_interval)

        # Add the remaining intervals
        result += intervals[i:]

        return result


def main():
    solution = Solution()
    result = solution.insert(intervals=[[1, 3], [6, 9]], new_interval=[2, 5])
    print(f"Result {result}")

    # [[1,5],[6,9]]

    result = solution.insert(intervals=[[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], new_interval=[4, 8])
    print(f"Result {result}")
    # [[1, 2], [3, 10], [12, 16]]

    result = solution.insert(intervals=[], new_interval=[5, 7])
    print(f"Result {result}")

    result = solution.insert(intervals=[[1, 5]], new_interval=[2, 3])
    print(f"Result {result}")

    result = solution.insert(intervals=[[1, 5]], new_interval=[0, 3])
    print(f"Result {result}")

    result = solution.insert(intervals=[[1, 5]], new_interval=[0, 0])
    print(f"Result {result}")


if __name__ == "__main__":
    main()