Problem

---

https://leetcode.com/problems/insert-interval/?envType=problem-list-v2&envId=rab78cw1

Solution

---

이 문제는 리트코드의 Grind 75의 Medium 문제로, 그리디 + 정렬 + 구간 개념이 합쳐진 문제다.

구간 문제의 특징:

• 시작점 / 끝점이 있음
• 겹침 / 비겹침으로 판단 가능
• 한 번 선택하면 이후에 미치는 영향이 단순함

현재 최선의 선택을 한다는 말은 조금 어렵다. 그냥 지금 당장 정답이라고 믿고 배팅을 하겠다로 이해하고 있다.
조합을 따지지도 않고, 나중에 뒤돌아보지도 않아도 괜찮을 유형이 그리디라고 할 수 있겠다.

배열을 Merge하자!

왜 이 문제가 어려웠냐면 길이가 가변적이었기 때문이었다.
무식하게도 리스트로 구현하고 배열로 바꿀 생각을 못했다. 아직도 인덱스 접근에 벌벌 떤다는 뜻이기도 했다.

그러면 리스트로 어떻게 머지를 진행할 것인가?
열쇠는 리스트의 마지막 요소에 있다. 우리는 계속 list.get(list.size()-1)[1]을 비교하고 값을 업데이트하는 과정을 계속할 것이다.

이 문제는 3단계로 나누어 공부했다.

• 초기화
  • intervals 원본 배열과 newInterval을 합친다.
    • intervals.length+1 배열을 만들어 마지막 자리에 newInterval을 넣어라.
  • int[][] 배열을 오름차순으로 정렬한다.
• 비교
  • 구간이 겹칩니까? 라는 조건을 표현할 것
    • 리스트가 비었다면 구간이 겹치지 않는다.
    • 리스트 마지막[1]이 주어지는 구간[0]보다 작다면 구간이 겹치지 않는다.
    • 그 외에는 구간이 겹치지 머지해야 한다. 머지할 때는 가장 넓은 구간이 리스트에 최종적으로 들어가게끔 해야 한다.
• 반환타입을 문제에 맞게 형변환
  • 리스트를 배열로 형변환해서 반환한다.

Code

---

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {

        int[][] arr = new int[intervals.length + 1][2];

        for (int i = 0; i < intervals.length; i++) {
            arr[i] = intervals[i];
        }

        arr[intervals.length] = newInterval;

        Arrays.sort(arr, (a,b) -> a[0] - b[0]);

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

        for(int[] interval : arr){
            if(result.isEmpty() || result.get(result.size()-1)[1] < interval[0]){
                result.add(interval);
            }else{
                result.get(result.size()-1)[1] = Math.max(result.get(result.size()-1)[1], interval[1]);
            }
        }

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