여러 영화 상영에 대한 간격 목록이 있다고 가정하고(겹칠 수 있음) 모든 영화를 상영하는 데 필요한 최소 극장 수를 찾아야 합니다.
따라서 입력이 간격 =[[20, 65],[0, 40],[50, 140]]과 같으면 출력은 [20, 65]와 [0, 40]이 겹치므로 2가 됩니다. . [20, 65]와 [50, 140]도 겹치지만 [0, 40]과 [50, 140]은 겹치지 않습니다. 따라서 2개의 극장이 필요합니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다.
- t :=새 목록
- 각 간격 [a, b] 간격에 대해, do
- t 끝에 [a, 1] 삽입
- t 끝에 [b, -1] 삽입
- ans :=0, count :=0
- 정렬된 형식의 t에 있는 각 쌍(x, d)에 대해 다음을 수행합니다.
- count :=count + d
- ans :=ans 및 count의 최대값
- 반환
더 나은 이해를 위해 다음 구현을 살펴보겠습니다.
예시 코드
class Solution: def solve(self, intervals): t = [] for a, b in intervals: t.append((a, 1)) t.append((b, -1)) ans = count = 0 for x, d in sorted(t): count += d ans = max(ans, count) return ans ob = Solution() intervals = [[20, 65],[0, 40],[50, 140]] print(ob.solve(intervals))
입력
[[20, 65],[0, 40],[50, 140]]
출력
2