Daily LeetCode Challenge - 57. Insert Interval

Problem From.
https://leetcode.com/problems/insert-interval/

오늘 문제는 주어진 intervals 배열에서 newInterval 배열을 넣는데, 겹치는 부분이 있으면 그 부분을 같이 포함하여 intervals 배열이 서로 겹치지않는 오름차순으로 정렬되도록 하는 문제였다.

문제에서 요구한 있는 그대로 풀 수 있었는데, 일단 비어있는 result 배열을 선언한뒤에,
newInterval 의 첫번째 원소보다 intervals 의 각 원소의 끝이 작다면 result 배열에 추가해준다.

그 다음 newInterval 과 겹치는 부분을 찾기 위해서, interval 의 시작점과 newInterval 의 시작점 중에서 작은 수를 새로운 interval 의 시작점으로 잡고, 마찬가지로 interval 의 끝점과 newInterval 의 끝점 중에서 큰 수를 새로운 interval 의 끝점으로 잡는다.

새로운 interval 을 result 배열에 넣어준 뒤에, 남아있는 intervals 를 result 배열에 넣어준다.

class Solution {
    fun insert(intervals: Array<IntArray>, newInterval: IntArray): Array<IntArray> {
        
        var insertInterval = newInterval
        var index = 0
        val result = arrayListOf<IntArray>()
        
        while(index < intervals.size && newInterval[0] > intervals[index][1]) {
            result.add(intervals[index])
            index += 1
        }
        while(index < intervals.size && newInterval[1] >= intervals[index][0]) {
            insertInterval = intArrayOf(
                Math.min(insertInterval[0], intervals[index][0]),
                Math.max(insertInterval[1], intervals[index][1])
            )
            index += 1
        }
        
        result.add(insertInterval)
        
        while(index < intervals.size) {
            result.add(intervals[index])
            index += 1
        }
        
        return result.toTypedArray()
    }
}

위 문제의 시간복잡도는 O(kN) 이 된다.