Insert Interval

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

Insert Interval - LeetCode

 

이전에 풀었던 Merge Intervals 문제와 거의 같은 문제이다. 단 두번째 매개변수로 하나의 Intervals를 추가해주어야 한다. 이전에 풀었던 방식에서 PriorityQueue에 신규 Intervals 만 추가해 주면 문제를 해결할 수 있었다. 이전에 풀었던 Merge Intervals는 아래와 같다.

 

https://blog.honey-sleep.co.kr/61

 

최종 코드는 아래와 같다.

public class Solution {  
    public int[][] insert(int[][] intervals, int[] newInterval) {  
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0] );  
        for(int[] interval:intervals){  
            pq.add(interval);  
        }  
        pq.add(newInterval); // newInterval 을 넣어준다.  
  
        List<int[]> newArray = new ArrayList<>();  
  
        while(!pq.isEmpty()){  
            int[] cur = pq.poll();  
            while(!pq.isEmpty() && pq.peek()[0] <= cur[1]){  
                int[] next = pq.poll();  
                cur[1] = Math.max(next[1], cur[1]);  
            }  
            newArray.add(cur);  
        }  
  
        int finalSize = newArray.size();  
        int[][] answer = new int[finalSize][2];  
  
        for(int i = 0; i < finalSize; i++){  
            answer[i][0] = newArray.get(i)[0];  
            answer[i][1] = newArray.get(i)[1];  
        }  
  
        return answer;  
    }  
}