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

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

중간

Given an array of intervals 간격 어디 간격[i] = [시작 _i , 끝 _i ], 반품 the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

예시 1:

입력: intervals = [[1,2],[2,3],[3,4],[1,3]]
산출: 1
설명: [1,3] can be removed and the rest of the intervals are non-overlapping.

예 2:

입력: intervals = [[1,2],[1,2],[1,2]]
산출: 2
설명: You need to remove two [1,2] to make the rest of the intervals non-overlapping.

예시 3:

입력: intervals = [[1,2],[2,3]]
산출: 0
설명: You don't need to remove any of the intervals since they're already non-overlapping.

제약:

1 <= intervals.length <= 10⁵
간격[i].길이 == 2
-5 * 10⁴ <= start_i < end_i <= 5 * 10⁴

파이썬

				
					# time complexity: O(nlogn)
# space complexity: O(n)
from typing import List


class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x: x[1])
        k = -float("inf")
        ans = 0
        for x, y in intervals:
            if x >= k:
                k = y
            else:
                ans += 1
        return ans


intervals = [[1, 2], [2, 3], [3, 4], [1, 3]]
print(Solution().eraseOverlapIntervals(intervals))

중간

파이썬

관련 기사