[LeetCode] 56. Merge Intervals 풀이 (Java)

✔️ 오늘의 리트코드 공부 기록 – Merge Intervals

---

문제 요약 (Merge Intervals)

여러 개의 interval이 주어진다.
각 interval은 [start, end] 형태이며,
서로 겹치는 구간들을 하나로 병합해서 반환해야 한다.

 

• 문제 링크: https://leetcode.com/problems/merge-intervals

---

🤔 처음 떠올린 아이디어

처음 문제를 봤을 때는 이런 생각이 들었다.

겹치는지 판단하려면,
interval들이 어떤 순서로 정렬돼 있으면 좋을까?

 

모든 interval을 서로 비교하면 복잡해진다.
그래서 비교 대상을 최소화할 수 있는 정렬 기준이 필요했다.

---

 

💡 핵심 깨달음: 시작점만 정렬하면 된다

겹침 여부의 조건은 단 하나다.

• 현재 interval의 start ≤ 이전 interval의 end

이 비교가 항상 성립하려면,
start가 작은 순서대로 정렬돼 있으면 된다.

나는 여기서 이렇게 정리했다.

• start 기준으로 정렬
• 이전 interval 하나만 보고 겹침 판단
• end는 항상 최대값만 유지

👉 이 문제는 결국
정렬 + 그리디 문제였다.

---

🧠 정렬 기준에 대한 고민

여기서 한 번 더 고민이 들었다.

start가 같은 경우엔 정렬 기준이 더 필요하지 않나?

 

결론부터 말하면 필수는 아니다.

• start가 같으면 무조건 겹친다.
• 병합 시 end = max(prevEnd, currEnd)를 하므로
• 순서가 달라도 결과는 동일하다

그래도 안정성을 위해 나는 이렇게 정리했다.

 

정렬 기준

• start 오름차순
• start가 같으면 end 오름차순

---

 

🔁 병합 로직 사고 과정

정렬된 interval을 왼쪽부터 순회한다.
현재까지 하나의 interval을 유지하면서:

1. ✅ 겹치는 경우
   currStart ≤ prevEnd
   → end = max(end, currEnd)
2. ❌ 안 겹치는 경우
   → 지금까지의 interval을 결과에 추가
   → 새로운 interval 시작

중요한 포인트는 이거 하나다.

항상 이전 interval 하나만 보고 판단한다

 

---

📌 흐름 정리

 

1. interval을 start 기준으로 정렬
2. 첫 interval로 start, end 초기화
3. 다음 interval부터 순회
   1. 겹치면 end 갱신
   2. 안 겹치면 결과에 추가 후 새로 시작
4. 마지막 interval 결과에 추가

 

---

 

코드 (Java)

 

class Solution {
    public int[][] merge(int[][] intervals) {
        // 1. 시작점 기준 정렬
        Arrays.sort(intervals, (a, b) -> {
            if (a[0] == b[0]) return a[1] - b[1];
            return a[0] - b[0];
        });

        List<int[]> result = new ArrayList<>();

        int start = intervals[0][0];
        int end = intervals[0][1];

        // 2. 순회하며 병합
        for (int i = 1; i < intervals.length; i++) {
            int currStart = intervals[i][0];
            int currEnd = intervals[i][1];

            // 겹치는 경우
            if (currStart <= end) {
                end = Math.max(end, currEnd);
            }
            // 안 겹치는 경우
            else {
                result.add(new int[]{start, end});
                start = currStart;
                end = currEnd;
            }
        }

        // 마지막 interval 추가
        result.add(new int[]{start, end});

        return result.toArray(new int[result.size()][]);
    }
}

 

📈 시간 / 공간 복잡도

시간 복잡도

• 정렬: O(N log N)
• 순회: O(N)
• 전체: O(N log N)

공간 복잡도

• 결과 리스트 사용 → O(N)

---

 

📝 이번 문제에서 얻은 깨달음

이 문제의 본질은
겹침 판단 로직이 아니라
👉 비교 대상을 하나로 줄이는 사고였다.

• start 정렬만 해두면
• 항상 “이전 interval 하나”만 비교하면 되고
• end는 최대값만 유지하면 된다

 

✨ 한 줄 정리

❌ 모든 경우를 비교할 필요는 없다
✅ 비교 대상을 하나로 줄일 수 있으면 그리디가 된다

 

Merge Intervals는
정렬 + 그리디 사고 연습용으로 정말 좋은 문제였다.