[LeetCode] 57. Insert Interval

문제 보기

Kotlin

O(nlogn) 시간 복잡도 해결법

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import kotlin.math.max

class Solution {
fun insert(intervals: Array<IntArray>, newInterval: IntArray): Array<IntArray> {
val new = intervals + newInterval
new.sortWith(compareBy {it[0]})

val arr = mutableListOf<IntArray>()

for (interval in new) {
if (arr.isEmpty() || arr.last()[1] < interval[0]) {
arr.add(interval)
} else {
arr.last()[1] = max(arr.last()[1], interval[1])
}
}

return arr.toTypedArray()
}
}

O(n) 시간 복잡도 해결법

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import kotlin.math.*

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

for (interval in intervals) {
if (interval[1] >= newInterval[0]) break
merged.add(interval)
i++
}

while (i < intervals.size && intervals[i][0] <= newInterval[1]){
newInterval[0] = min(newInterval[0], intervals[i][0])
newInterval[1] = max(newInterval[1], intervals[i][1])
i++
}

merged.add(newInterval)

while (i < intervals.size){
merged.add(intervals[i])
i++
}

return merged.toTypedArray()
}
}

댓글