57. Insert Interval

문제)

57. Insert Interval

 

You are given an array of non-overlapping intervals intervals where intervals[i] = [starti, endi] represent the start and the end of the ith interval and intervals is sorted in ascending order by starti. You are also given an interval newInterval = [start, end] that represents the start and end of another interval.

Insert newInterval into intervals such that intervals is still sorted in ascending order by starti and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).

Return intervals after the insertion.

 

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

 

Constraints:

• 0 <= intervals.length <= 104
• intervals[i].length == 2
• 0 <= starti <= endi <= 105
• intervals is sorted by starti in ascending order.
• newInterval.length == 2
• 0 <= start <= end <= 105

솔루션1)

- 두 개의 리스트를 생성

- newInterval에 머지되는 경우와 아닌 경우라 나눔

- newInterval에 머지되는 경우에 값들은 최종적으로 min, max를 구해서 새로운 인터벌을 생성

- 새로운 인터벌은 머지 안되는 아이템과 합쳐서 정렬한 결과를 리턴

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        merged = []
        not_merged = []
        for interval in intervals:
            s, e = interval
            if s <= newInterval[0] <= e or s <= newInterval[1] <= e:       
                # 머지 case
                merged.append(interval)
            elif newInterval[0] <= s and e <= newInterval[1]:                            
                # 머지 case
                merged.append(interval)
            else:          
                # 머지 안되는 case
                not_merged.append(interval)
        
        # 머지 case에 newInterval을 포함
        merged.append(newInterval)              
        
        # 머지 case에서 start 값과 end 값을 구성하는 새로운 interval을 생성
        trans_merged = list(zip(*merged))
        merged_interval = [min(trans_merged[0]), max(trans_merged[1])]        
        
        not_merged.append(merged_interval)
        not_merged.sort()
        return not_merged