LC 56 & LC 57

Solutions to LeetCode 56 Merge Interval and LeetCode 57 Insert Interval.

LeetCode 56

Merge Interval (Medium). [link]

Time complexity O(n log n) where n is the number of intervals. It takes O(log n) to sort the intervals and O(n) to iterate through all intervals. Space complexity O(log n) is taken by sorting.

class Solution(object):
    def merge(self, intervals):
        """
        :type intervals: List[List[int]]
        :rtype: List[List[int]]
        """
        res = []
        intervals = sorted(intervals, key = lambda x: x[0]) 
        for i in intervals: # sort intervals by the first value
            if not res or i[0] > res[-1][-1]: # if no overlap, append
                res.append(i)
            else: # if overlap, enlarge the upper bound
                res[-1][-1] = max(res[-1][-1], i[-1])
        return res

Note: intervals.sort(key = lambda x: x[0]) is the same as intervals = sorted(intervals, key = lambda x: x[0]) .

LeetCode 57

Insert Interval (Medium). [link]

1. Apply the method in LeetCode 56.

   Time complexity O(n). Space complexity O(n).

class Solution(object):
    def insert(self, intervals, newInterval):
        """
        :type intervals: List[List[int]]
        :type newInterval: List[int]
        :rtype: List[List[int]]
        """
        index = len(intervals)
        for i in range(index): # find the index of new interval
            if newInterval[0] < intervals[i][0]:
                index = i
                break
                
        intervals.insert(index, newInterval) # add new interval into the list

        res = []
        for i in intervals: # same as LC56, except intervals are already sorted
            if not res or i[0] > res[-1][-1]:
                res.append(i)
            else:
                res[-1][-1] = max(res[-1][-1], i[-1])
        return res

2. Find and merge the overlapping set.

   Time complexity O(n). Space complexity O(n).

class Solution(object):
    def insert(self, intervals, newInterval):
        """
        :type intervals: List[List[int]]
        :type newInterval: List[int]
        :rtype: List[List[int]]
        """
        start, end = newInterval[0], newInterval[-1]
        res, l, r = [], [], []
        
        for i in intervals:
            if i[-1] < start:
                l.append(i)
            elif i[0] > end:
                r.append(i)
            else: # if overlaps
                start = min(start, i[0])
                end = max(end, i[-1])
                
        if len(l) != 0:
            res.extend(l) # add a list of lists
        res.append([start, end])
        if len(r) != 0:
            res.extend(r) # add a list of lists
        
        return res