Funcia
Lv.2arraysorting

겹치는 구간 합치기

메모리 제한
256 MB
정확성 시간 제한
10000 ms
푼 사람
0
0

닫힌 구간들의 배열 intervals가 주어집니다. intervals[i] = [start, end]는 start 이상 end 이하의 구간입니다.

겹치거나 끝점이 맞닿는 구간들을 모두 하나로 합친 결과를 반환하세요. 결과는 start 오름차순으로 정렬해야 합니다.

  • [1, 3]과 [3, 5]는 3에서 맞닿으므로 [1, 5]로 합칩니다.
  • [1, 2]와 [3, 4]는 사이에 빈 곳(2와 3 사이)이 있으므로 합치지 않습니다.

입출력 예

intervalsresult
[[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[][]

제한 사항

  • 1≤1 \le intervals.length ≤200,000\le 200{,}000
  • intervals[i] = [start, end], 0≤start≤end≤1090 \le start \le end \le 10^9
  • 입력 구간은 정렬되어 있지 않고, 같은 구간이 여러 번 나올 수 있습니다.

기대 복잡도

시간
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이어야 합니다.

복잡도 목표

모든 구간 쌍을 비교하며 합치는 O(N2)O(N^2) 풀이는 효율성 테스트에서 시간 초과가 납니다. 정렬 O(Nlog⁡N)O(N \log N) 후 한 번 훑는 풀이가 필요합니다.

언어별 시간 제한

언어효율성 시간 제한
C (GCC, gnu17)298 ms추정
C++ (GCC, gnu++23)298 ms도출됨
Python 3.131000 ms도출됨
Java 253244 ms도출됨
Kotlin 2.4 (JVM)1596 ms추정
C# 14 (.NET 10)1596 ms추정

테스트 그룹

그룹배점테스트 수공개 범위
sample03입력·출력 공개
correctness4010판정만
performance604판정만
에디터 불러오는 중…

아직 결과가 없습니다. 실행 또는 제출하세요.