Funcia
Lv.2arrayintervalstwo-pointers

두 사람이 함께 비는 시간

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

두 사람이 각자 비어 있는 시간대를 정리해 왔습니다. first와 second의 각 원소 [start, end]는 start부터 end까지(양 끝 포함) 시간이 빈다는 뜻입니다. 각 목록 안의 시간대는 시작 시각 순으로 정렬되어 있고 서로 겹치거나 맞닿지 않습니다(앞 구간의 end < 다음 구간의 start).

두 사람이 동시에 비어 있는 시간대를 모두 구해 시작 시각 순으로 반환하세요. 두 구간이 한 시각에서만 만나면 [t, t]처럼 길이 0인 구간도 포함합니다. 겹치는 시간이 없으면 빈 배열을 반환합니다.

입출력 예

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

제한 사항

  • 1≤1 \le first.length, second.length ≤100,000\le 100{,}000
  • 각 원소는 [start, end]이며 0≤0 \le start ≤\le end ≤109\le 10^9
  • 각 목록 안에서 i번째 구간의 end < i+1번째 구간의 start

기대 복잡도

시간
O(N + M)
공간
O(N + M)

입출력 예

firstsecond기대 출력
[[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)일 때만 존재합니다.

두 목록이 모두 정렬되어 있으므로 병합 정렬처럼 포인터 두 개를 앞에서부터 움직이면 됩니다. 현재 두 구간의 교집합을 확인한 뒤, 끝이 먼저 끝나는 쪽의 포인터를 한 칸 옮깁니다. 그 구간은 상대 목록의 다음 구간과는 겹칠 수 없기 때문입니다.

전체 O(N+M)O(N + M)입니다. 모든 쌍을 비교하는 O(NM)O(NM) 풀이는 시간 초과가 납니다.

언어별 시간 제한

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

테스트 그룹

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

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