[LeetCode#56] Merge Intervals

 

❒ Description

---

날짜	2024.09.27 (금)
레벨	Medium
제목	Merge Intervals
링크	https://leetcode.com/problems/merge-intervals/description/
알고리즘	정렬
시간 복잡도	O(NlonN)

 

 

 

 

 

 

❒ 문제 및 로직 분석

---

이번 문제는 겹치는 구간을 판단하는 아이디어가 필요한 문제이다.

int[][] intervals = { {1, 3}, {8, 11}, {2, 6}, {15, 18} }

i번 째 배열의 1번 째 요소와 i + 1 번째 배열의 0번 째 요소를 비교하면 겹침 여부를 판단할 수 있다.

※ 겹치는 경우
i 번째 배열의 1번 째 요소 >= i + 1 번째 배열의 0번 째 요소

1. Range1과 Range2가 겹치는 범위인지 판단
2. 겹치는 경우라고 판단이 됐다면, 새로운 범위를 지정해줘야 한다.
   • 겹치는 경우가 아니라면 Range1은 결과 배열에 삽입한다.
3. {1, 5}, {2, 4} 와 같은 case 처럼 아예 포함되는 경우도 고려해야 한다.
4. 따라서 새로운 범위는 Range1 유지 또는 { Range1[0], Range2[1] } 로 지정한다. 

 

 

 

 

❒ Solution

---

1. Deque 사용

public int[][] merge(int[][] intervals) {
    // 예외 처리
    if (intervals.length == 0) return intervals;
    
    // interval 관리를 위해 deque 선언 
    Deque<int[]> q = new LinkedList<>();
    
    // start point를 기준으로 오름차순 정렬
    Arrays.sort(intervals, Comparator.comparingInt(interval -> interval[0]));

    // 정렬 후 deque에 삽입
    for (int[] interval : intervals) {
        q.offer(interval);
    }
    
    // 결과 배열 선언
    List<int[]> result = new ArrayList<>();

    // q의 사이즈가 1 이하일 때 까지 while문 반복 
    while (q.size() > 1) {
        int[] interval1 = q.pollFirst();
        int[] interval2 = q.pollFirst();
        if (interval2 != null && interval1[1] >= interval2[0]) {
            // 겹치는 경우
            q.addFirst(new int[]{interval1[0], Math.max(interval1[1], interval2[1])});
        } else {
            // 겹치지 않는 경우
            result.add(interval1);
            q.addFirst(interval2);
        }
    }
    
    // 항상 q에는 마지막 범위가 남아있기 때문에
    result.add(q.poll());
    return result.toArray(new int[result.size()][2]);
}

 

 

 

2. 오직 배열만 사용

public int[][] merge(int[][] intervals) {
    if (intervals.length == 0) return intervals;
    Arrays.sort(intervals, Comparator.comparingInt(interval -> interval[0]));
   
    List<int[]> result = new ArrayList<>();
    
    // 현재 Interval 꺼내기
    int[] currInterval = intervals[0];
    for (int i = 1; i < intervals.length; i++) {
        int[] nextInterval = intervals[i];
        if (currInterval[1] >= nextInterval[0]) {
            // 겹치는 경우
            currInterval[1] = Math.max(currInterval[1], nextInterval[1]);
        } else {
            // 겹치지 않는 경우, currInterval 갱신
            result.add(currInterval);
            currInterval = nextInterval; 
        }
    }
    result.add(currInterval);
    return result.toArray(new int[result.size()][2]);
}

 

 

 

 

 

 

---