여러 개의 구간(interval) 리스트와 작업 유형(types) 문자열 리스트가 주어졌다고 가정해 보겠습니다. 각 구간은 [start, end) 형태이며, intervals[i]는 누군가 types[i]라는 작업을 start부터 end 직전까지 수행했음을 의미합니다. 단, 같은 유형의 두 구간은 서로 겹치거나 맞닿지 않는다는 조건이 있습니다.
우리가 구해야 할 것은 정렬된 병합 리스트입니다. 각 항목은 [start, end, num_types] 형태로, start부터 end 사이에 num_types개의 작업이 동시에 진행되고 있었음을 나타냅니다.
예시로 이해하기
다음과 같은 입력이 주어졌다고 해보겠습니다.
intervals = [[0, 3], [5, 7], [0, 7]] types = ["problem solving", "news", "game play"]
이때 출력은 [[0, 3, 2], [3, 5, 1], [5, 7, 2]]가 됩니다. 그 이유는 다음과 같습니다.
- [0, 3): "problem solving"과 "game play"가 동시에 진행 → 2개
- [3, 5): "game play"만 진행 → 1개
- [5, 7): "news"와 "game play"가 동시에 진행 → 2개
접근 방법: 이벤트 스위핑(Sweep Line)
이 문제는 스윕 라인(sweep line) 기법으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 간단합니다. 구간의 시작 지점에서는 활성 작업 수를 1 증가시키고, 종료 지점에서는 1 감소시키는 이벤트를 만든 뒤, 시간 순서대로 이벤트를 훑으면서 구간별 활성 작업 수를 집계하는 것입니다.
구체적인 단계는 다음과 같습니다.
ev := 새로운 이벤트 리스트를 생성합니다.
intervals의 각 구간 쌍 (s, e)에 대해 다음을 수행합니다.
- (s, +1)을 ev의 끝에 추가합니다. (작업 시작 이벤트)
- (e, −1)을 ev의 끝에 추가합니다. (작업 종료 이벤트)
ev를 오름차순으로 정렬합니다.
cnt := 0, last := −1로 초기화합니다.
ans := 결과를 담을 새로운 리스트를 생성합니다.
ev의 각 이벤트 (t, inc)에 대해 다음을 수행합니다.
- t가 last와 다르고 cnt가 0이 아니면, [last, t, cnt]를 ans에 추가합니다.
- cnt에 inc를 더합니다.
- last := t로 갱신합니다.
ans를 반환합니다.
구현 예제
아래 코드를 통해 더 잘 이해해 보겠습니다.
class Solution:
def solve(self, intervals, jobs):
ev = []
for s, e in intervals:
ev.append((s, 1))
ev.append((e, -1))
ev.sort()
cnt = 0
last = -1
ans = []
for t, inc in ev:
if t != last and cnt != 0:
ans.append([last, t, cnt])
cnt += inc
last = t
return ans
ob = Solution()
intervals = [
[0, 3],
[5, 7],
[0, 7]
]
types = ["problem solving", "news", "game play"]
print(ob.solve(intervals, types))
입력
[[0, 3],[5, 7],[0, 7]], ["problem solving", "news", "game play"]
출력
[[0, 3, 2], [3, 5, 1], [5, 7, 2]]
복잡도 분석
n개의 구간이 주어질 때, 이벤트는 총 2n개 생성되며 정렬에 O(n log n)의 시간이 소요됩니다. 이후 스윕 과정은 O(n)이므로 전체 시간 복잡도는 O(n log n)입니다. 공간 복잡도는 이벤트 리스트와 결과 리스트 저장을 위해 O(n)입니다.