Merge Intervals

꿀잠마스터 2026. 8. 7. 01:14

https://leetcode.com/problems/merge-intervals/submissions/2096919730/

Merge Intervals - LeetCode

Can you solve this real interview question? Merge Intervals - Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input

leetcode.com

간격들이 주어졌을 때 서로 겹칠 수 있는 간격이면 합쳐서 최대한 압축한 형태의 간격 집합을 정답으로 내는 문제이다.

두 간격이 있을 때 겹친다고 하는 것은 앞 간격의 끝 값이 뒷 간격의 첫 값을 넘어서면 된다고 정의할 수 있다.

이 때 비교하는 두 간격을 정하기 위해서 간격의 앞 부분을 기준으로 순서대로 나열하면 차례대로 비교할 수 있다고 생각하고 PriorityQueue를 사용하였다. PriorityQueue에 간격 값들을 넣은 후 하나 씩 꺼내서 이어질때까지 잇는 작업을 while 문을 통해 진행한 이후 정답 List에 넣어 주었다. 최종적으로 배열화하여 return 하였다.

import java.util.*;  
  
public class Solution {  
    public int[][] merge(int[][] intervals) {  
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0] );  
        for(int[] interval:intervals){  
            pq.add(interval);  
        }  
  
        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;  
    }  
}