[Leetcode] 0435. 겹치지 않는 간격

Python, C++, JavaScript, SQL 및 TypeScript의 다양한 LeetCode 솔루션을 살펴보세요. 여러 프로그래밍 언어로 인터뷰 준비, 학습 및 코드 연습에 적합합니다. Github 레포 링크

중간

간격의 배열이 주어지면 간격 어디 간격[i] = [시작 _i , 끝 _i ], 반품 나머지 구간이 겹치지 않도록 하기 위해 제거해야 하는 최소 구간 수.

예시 1:

입력: 간격 = [[1,2],[2,3],[3,4],[1,3]]
산출: 1
설명: [1,3]은 제거할 수 있으며 나머지 간격은 겹치지 않습니다.

예 2:

입력: 간격 = [[1,2],[1,2],[1,2]]
산출: 2
설명: 나머지 구간이 겹치지 않게 하려면 두 개의 [1,2]를 제거해야 합니다.

예시 3:

입력: 간격 = [[1,2],[2,3]]
산출: 0
설명: 간격은 이미 겹치지 않으므로 간격을 제거할 필요가 없습니다.

제약:

1 <= 간격.길이 <= 10 ⁵
간격[i].길이 == 2
-5 * 10 ⁴ <= 시작 _i < 끝 _i <= 5 * 10 ⁴

파이썬

				
					# 시간 복잡도: O(nlogn) # 공간 복잡도: O(n) 입력 가져오기 목록 클래스 솔루션: def erasureOverlapIntervals(self, 간격: List[List[int]]) -> int: Intervals.sort(key=lambda x : x[1]) k = -float("inf") ans = 0 간격의 x, y에 대해: if x >= k: k = y else: ans += 1 return ans 간격 = [[1, 2] , [2, 3], [3, 4], [1, 3]] print(Solution().eraseOverlapIntervals(간격))

중간

파이썬

관련 기사