LeetCode 57(Insert Interval, Python)

1. 문제 링크

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

Insert Interval - LeetCode

 

2. 문제 설명

• 주어진 배열 intervals는 시작과 끝을 나타내는 요소들을 가지고 있고, 새로운 interval을 나타내는 newInterval이 주어졌을 때,
• 이를 intervals에 삽입하여, 삽입 후의 intervals를 반환
  • 단, intervals는 시작 값이 오름차순으로 정렬되어 있어야 하며, 겹치는 구간이 없도록 삽입을 해야 함. 
  • 겹치는 구간이 있다면 그것들을 합쳐야 함. (직전 문제와 유사한 문제)
• 예시1) intervals=[[1,3],[6,9]], newInterval=[2,5]일 때, output=[[1,5],[6,9]]
• 예시2) intervals=[[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval=[4,8] 이면 output=[[1,2],[3,10],[12,16]]
  • 왜냐하면 newInterval인 [4,8]은 [3,5], [6,7], [8,10]과 overlap 되기 때문 

3. 처음 풀이 

• leetcode 직전 문제인 "Merge Intervals"에 하나의 변화만 주어 코드 작성
  • newInterval을 intervals에 append 시킨 후, 이를 sort()시킨 이후에, Merge Intervals와 유사하게 풀이
    • merged 라는 array를 만들어두고, 
      • interval element의 첫번째 값이 merged array의 마지막 element의 두번째 값보다 작거나 같으면, merged[-1][1] 값을 업데이트하고, 그 외의 경우는 [start,end]를 append 하여
    • 최종적으로 merged array 반환

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:

        intervals.append(newInterval)
        intervals.sort()

        merged = [intervals[0]]
        
        for start, end in intervals[1:]:
            if start<=merged[-1][1]:
                merged[-1][1] = max(merged[-1][1], end)
            else:
                merged.append([start, end])
                
        return merged

 

4. 다른 풀이

• submission에서 runtime이 높았던 풀이

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