[LeetCode] 57. Insert Interval

Link : https://leetcode.com/problems/insert-interval/

문제 정의

You are given an array of non-overlapping intervals intervals where intervals[i] = [start<sub>i</sub>, end<sub>i</sub>] represent the start and the end of the i<sup>th</sup> interval and intervals is sorted in ascending order by start<sub>i</sub>. You are also given an interval newInterval = [start, end] that represents the start and end of another interval.

Insert newInterval into intervals such that intervals is still sorted in ascending order by start<sub>i</sub> and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).

Return intervals after the insertion.

Note that you don't need to modify intervals in-place. You can make a new array and return it.

Example 1:

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

Example 2:

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

Constraints:

• 0 <= intervals.length <= 10<sup>4</sup>

• intervals[i].length == 2

• 0 <= start<sub>i</sub> <= end<sub>i</sub> <= 10<sup>5</sup>

• intervals is sorted by start<sub>i</sub> in ascending order.

• newInterval.length == 2

• 0 <= start <= end <= 10<sup>5</sup>

문제 분석

결국 문제는 이미 overlap 되어있지 않은 순수한 입력값이 존재하고 중간에 overlap 될 수 있는 값을 어떻게 넣을 것인가에 대한 내용으로 보입니다.

그래서 저는 다음과 같은 방식으로 풀어보려고 했습니다

1. 중간에 넣어야하는 값을 넣기 위해서 index 찾기 수행 및 answer에 insert

2. 값을 넣기 전에 overlap이 되는지 확인

   1. 만약 overlap 되는 경우, 값을 merge

   2. 아닌 경우, 값을 insert

3. 나머지 값들을 끝까지 순회 및 insert

문제 해결

import kotlin.math.max
import kotlin.math.min

class Solution {
    fun insert(intervals: Array<IntArray>, newInterval: IntArray): Array<IntArray> {
        val result = mutableListOf<IntArray>()
        var i = 0
        val n = intervals.size

        while (i < n && intervals[i][1] < newInterval[0]) result.add(intervals[i++])

        var merged = newInterval
        while (i < n && intervals[i][0] <= merged[1]) {
            merged[0] = min(merged[0], intervals[i][0])
            merged[1] = max(merged[1], intervals[i][1])
            i++
        }
        result.add(merged)

        while (i < n) result.add(intervals[i++])

        return result.toTypedArray()
    }
}

느낀점

문제 자체는 어렵지 않지만 내용을 이해하고 해당 문제를 어떻게 해결할 것 인지 이해하는 과정이 중요한 포인트 였던 것 같습니다. 또한 leet code에서 문제를 풀다보면 영어 단어들이 한국어와 다르기 때문에 단어가 주는 직관적인 의미를 분석하기 어려운데 이제 블로그 글을 작성하면서 관련된 내용도 같이 넣는 것이 좋을 것 같다고 생각이 되어서 다음부터는 실천해보려고 합니다.