두 사람이 함께 비는 시간
- 메모리 제한
- 256 MB
- 정확성 시간 제한
- 10000 ms
- 푼 사람
- 0
두 사람이 각자 비어 있는 시간대를 정리해 왔습니다. first와 second의 각 원소 [start, end]는
start부터 end까지(양 끝 포함) 시간이 빈다는 뜻입니다. 각 목록 안의 시간대는 시작 시각 순으로 정렬되어 있고
서로 겹치거나 맞닿지 않습니다(앞 구간의 end < 다음 구간의 start).
두 사람이 동시에 비어 있는 시간대를 모두 구해 시작 시각 순으로 반환하세요. 두 구간이 한 시각에서만 만나면
[t, t]처럼 길이 0인 구간도 포함합니다. 겹치는 시간이 없으면 빈 배열을 반환합니다.
입출력 예
| first | second | result |
|---|---|---|
[[0, 2], [5, 10], [13, 23], [24, 25]] | [[1, 5], [8, 12], [15, 24], [25, 26]] | [[1, 2], [5, 5], [8, 10], [15, 23], [24, 24], [25, 25]] |
[[1, 3], [5, 9]] | [[10, 12]] | [] |
[[1, 7]] | [[3, 10]] | [[3, 7]] |
입출력 예 설명
예 1 — 예를 들어 [5, 10]과 [1, 5]는 시각 5에서만 만나 [5, 5]가 되고, [13, 23]과 [15, 24]는 [15, 23]에서 겹칩니다.
예 2 — second의 유일한 구간은 first의 모든 구간보다 늦습니다.
예 3 — 두 구간의 겹치는 부분은 [3, 7]입니다.
효율성
이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.
함수 시그니처
solution(first: int[][], second: int[][]) → int[][]
제한 사항
-
first.length,second.length - 각 원소는
[start, end]이며startend - 각 목록 안에서
i번째 구간의end<i+1번째 구간의start
기대 복잡도
- 시간
- O(N + M)
- 공간
- O(N + M)
입출력 예
| first | second | 기대 출력 |
|---|---|---|
[[0,2],[5,10],[13,23],[24,25]] | [[1,5],[8,12],[15,24],[25,26]] | [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]] |
[[1,3],[5,9]] | [[10,12]] | [] |
[[1,7]] | [[3,10]] | [[3,7]] |
힌트
힌트
두 구간 [a, b]와 [c, d]의 교집합은 [max(a, c), min(b, d)]이며, max(a, c) ≤ min(b, d)일 때만 존재합니다.
두 목록이 모두 정렬되어 있으므로 병합 정렬처럼 포인터 두 개를 앞에서부터 움직이면 됩니다. 현재 두 구간의 교집합을 확인한 뒤, 끝이 먼저 끝나는 쪽의 포인터를 한 칸 옮깁니다. 그 구간은 상대 목록의 다음 구간과는 겹칠 수 없기 때문입니다.
전체 입니다. 모든 쌍을 비교하는 풀이는 시간 초과가 납니다.
언어별 시간 제한
| 언어 | 효율성 시간 제한 | |
|---|---|---|
| C (GCC, gnu17) | 240 ms | 추정 |
| C++ (GCC, gnu++23) | 240 ms | 도출됨 |
| Python 3.13 | 1000 ms | 도출됨 |
| Java 25 | 2686 ms | 도출됨 |
| Kotlin 2.4 (JVM) | 1480 ms | 추정 |
| C# 14 (.NET 10) | 1480 ms | 추정 |
테스트 그룹
| 그룹 | 배점 | 테스트 수 | 공개 범위 |
|---|---|---|---|
| sample | 0 | 3 | 입력·출력 공개 |
| correctness | 40 | 12 | 판정만 |
| performance | 60 | 4 | 판정만 |