각 간격이 [start, end)와 같은 간격 목록이 있고 유형이라는 문자열 목록도 있다고 가정합니다. 이제 주어진 i에 대해 간격[i]은 누군가가 [시작, 종료)부터 작업 유형[i]에 대해 작업한 시간을 보여줍니다. 동일한 유형의 두 간격은 겹치거나 접촉하지 않습니다. 따라서 각 항목에 [start, end, num_types]가 있고 처음부터 끝까지 num_types개의 작업이 진행 중임을 나타내는 정렬된 병합 목록을 찾아야 합니다.
따라서 입력이 간격 =[ [0, 3], [5, 7], [0, 7] ] 유형 =["문제 해결", "뉴스","게임 플레이"]인 경우 출력은 다음과 같은 몇 가지 유형의 작업이 수행되므로 [[0, 3, 2], [3, 5, 1],[5, 7, 2]]가 됩니다. [0, 3) "문제 해결"과 " 게임 플레이", [3, 5) "게임 플레이" 사이, 그리고 [5, 7) "뉴스"와 "게임 플레이" 사이.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
ev :=새 목록
-
간격의 각 간격 시작 끝 쌍(s, e)에 대해 수행
-
ev
끝에 (s, 1) 삽입 -
ev
끝에 (e, −1) 삽입
-
-
목록 정렬 ev
-
cnt :=0, 마지막 :=−1
-
ans :=새 목록
-
ev에서 이벤트(t, inc)의 각 시간 및 증분 매개변수에 대해 수행
-
t가 last와 같지 않고 cnt가 0과 같지 않으면
-
cnt :=cnt + Inc
-
-
마지막 :=t
-
-
반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예
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]]