LeetCode #57: Insert Interval

https://leetcode.com/problems/insert-interval/description/

To solve this problem, we can iterate over the intervals in the list, and compare them with the new interval to see if there is any overlap. There are three possibilities for each interval:

1. No overlap and the new interval is smaller, so we add the new interval to the list before the current interval
2. No overlap and the new interval is larger, so we add the current interval to the result list
3. Overlap, so we merge the new interval with the current interval, and continue the iteration

After iterating over all the intervals, we add the new merged interval to the result list.

Here are the steps to solve the problem:

1. Create an empty result list
2. Iterate over the intervals in the input list
3. For each interval, compare it with the new interval
4. If there is no overlap and the new interval is smaller, add the new interval to the result list and return the result list
5. If there is no overlap and the new interval is larger, add the current interval to the result list
6. If there is an overlap, merge the new interval with the current interval and continue the iteration
7. After iterating over all the intervals, add the new merged interval to the result list and return the result list

Here is the solution in python3:

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        res = []
        for i in range(len(intervals)):
            if newInterval[1] < intervals[i][0]:
                res.append(newInterval)
                return res + intervals[i:]
            elif newInterval[0] > intervals[i][1]:
                res.append(intervals[i])
            else:
                newInterval = [min(newInterval[0], intervals[i][0]),              max(newInterval[1], intervals[i][1])]
        res.append(newInterval)
        return res
         

Time and Space Complexity

The time complexity of this solution is O(n), where n is the number of intervals in the input list. The space complexity is O(n), since we may need to add all the intervals to the result list.