Lv.2arraysorting
겹치는 구간 합치기
- 메모리 제한
- 256 MB
- 정확성 시간 제한
- 10000 ms
- 푼 사람
- 0
닫힌 구간들의 배열 intervals가 주어집니다. intervals[i] = [start, end]는 start 이상 end 이하의 구간입니다.
겹치거나 끝점이 맞닿는 구간들을 모두 하나로 합친 결과를 반환하세요. 결과는 start 오름차순으로 정렬해야 합니다.
[1, 3]과[3, 5]는 3에서 맞닿으므로[1, 5]로 합칩니다.[1, 2]와[3, 4]는 사이에 빈 곳(2와 3 사이)이 있으므로 합치지 않습니다.
입출력 예
| intervals | result |
|---|---|
[[1, 3], [8, 10], [2, 6], [15, 18]] | [[1, 6], [8, 10], [15, 18]] |
[[1, 4], [4, 5]] | [[1, 5]] |
[[5, 7], [1, 2], [3, 4]] | [[1, 2], [3, 4], [5, 7]] |
입출력 예 설명
예 1 — [1, 3]과 [2, 6]이 겹쳐 [1, 6]이 됩니다. 나머지는 다른 구간과 겹치지 않습니다.
예 2 — 4에서 맞닿으므로 하나로 합칩니다.
예 3 — 어떤 구간도 겹치지 않으니 정렬만 해서 반환합니다.
효율성
이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.
함수 시그니처
solution(intervals: int[][]) → int[][]
제한 사항
-
intervals.length intervals[i] = [start, end],- 입력 구간은 정렬되어 있지 않고, 같은 구간이 여러 번 나올 수 있습니다.
기대 복잡도
- 시간
- O(N log N)
- 공간
- O(N)
입출력 예
| intervals | 기대 출력 |
|---|---|
[[1,3],[8,10],[2,6],[15,18]] | [[1,6],[8,10],[15,18]] |
[[1,4],[4,5]] | [[1,5]] |
[[5,7],[1,2],[3,4]] | [[1,2],[3,4],[5,7]] |
힌트
힌트
구간을 시작점 기준으로 정렬하면, 합쳐질 구간들은 반드시 연속해서 나타납니다.
정렬한 뒤 앞에서부터 보면서 "지금 만들고 있는 구간" [curS, curE]를 유지하세요.
- 다음 구간의 시작이
curE이하면 겹치거나 맞닿은 것이니curE = max(curE, end)로 늘립니다. - 아니면 지금 구간을 결과에 넣고 새 구간을 시작합니다.
curE를 갱신할 때 max를 빼먹기 쉽습니다. [1, 10] 다음에 [2, 3]이 오면 끝은 그대로 10이어야 합니다.
복잡도 목표
모든 구간 쌍을 비교하며 합치는 풀이는 효율성 테스트에서 시간 초과가 납니다. 정렬 후 한 번 훑는 풀이가 필요합니다.
언어별 시간 제한
| 언어 | 효율성 시간 제한 | |
|---|---|---|
| C (GCC, gnu17) | 298 ms | 추정 |
| C++ (GCC, gnu++23) | 298 ms | 도출됨 |
| Python 3.13 | 1000 ms | 도출됨 |
| Java 25 | 3244 ms | 도출됨 |
| Kotlin 2.4 (JVM) | 1596 ms | 추정 |
| C# 14 (.NET 10) | 1596 ms | 추정 |
테스트 그룹
| 그룹 | 배점 | 테스트 수 | 공개 범위 |
|---|---|---|---|
| sample | 0 | 3 | 입력·출력 공개 |
| correctness | 40 | 10 | 판정만 |
| performance | 60 | 4 | 판정만 |