[LeetCode] 56. Merge Intervals

56. Merge Intervals

LeetCode

https://leetcode.com/problems/merge-intervals/description/

Merge Intervals - LeetCode

 

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.

intervals[i] = [starti, endi]인 구간(intervals) 배열이 주어졌을 때, 겹치는 모든 구간을 병합하고 입력된 모든 구간을 포함하는 겹치지 않는 구간의 배열을 반환하세요.

 

Example

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

Input: intervals = [[4,7],[1,4]]
Output: [[1,7]]
Explanation: Intervals [1,4] and [4,7] are considered overlapping.

---

1. 문제 요구사항 분석

겹치는 구간 병합

2. 접근 전략

😁 정렬 후 병합

1. 배열 정렬

2. 배열 for문 돌면서 병합

import java.util.*;

class Solution {
    public int[][] merge(int[][] intervals) {
        List<int[]> answer = new ArrayList<>();

        Arrays.sort(intervals, (o1, o2) -> {
            if (o1 != o2) return o1[0] - o2[0];
            else return o1[1] - o2[1];
        });

        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i - 1][1] >= intervals[i][0]) {
                intervals[i][0] = intervals[i - 1][0];
                intervals[i][1] = intervals[i - 1][1] < intervals[i][1] ? intervals[i][1] : intervals[i - 1][1];
            } else {
                answer.add(intervals[i - 1]);
            }
        }

        answer.add(intervals[intervals.length - 1]);

        return answer.stream().toArray(int[][]::new);
    }
}

 

🤩 좀 더 간단하고 최적화된 코드 작성

(위 버전은 Stream 사용으로 인한 미세한 오버헤드 발생 위험이 있음)

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals,(a,b)->Integer.compare(a[0],b[0]));
        
        List<int[]> list = new ArrayList<>();
        int[] prev = intervals[0];
        for(int i = 1; i < intervals.length; i++){
            if(intervals[i][0] <= prev[1]){
                prev[1] = Math.max(prev[1], intervals[i][1]);
            }else{
                list.add(prev);
                prev = intervals[i];
            }
        }
        list.add(prev);
        return list.toArray(new int[list.size()][]);
    }
}