[1스4코2파] # 243. LeetCode 435. Non-overlapping Intervals

[1스4코2파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 2명의 파이썬 개발자코딩 테스트 서막 : 1스4코1파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (243일차)
[4코1파] 2023.01.13~ (235일차)
[1스4코1파] 2023.04.12~ (146일차)
[1스4코2파] 2023.05.03 ~ (124일차)

Today :

2023.09.03 [243일차]
LeetCode 56. Merge Intervals
https://leetcode.com/problems/non-overlapping-intervals/

435. Non-overlapping Intervals

문제 설명

interval 배열이 주어질 때 겹치지 않는 interval 요소들을 남기기위해 최소로 삭제해야 하는 interval 수를 return 함

문제 풀이 방법

반대로 겹치지 않는 구간을 세고, 전체 구간의 수에서 빼주고,
겹치지 않는 구간을 구하기 위해서 먼저 구간의 end를 기준으로 오름차순으로 정렬하고, 이전 구간 end가 다음 구간 start이라면 다음 구간과 겹치지 않는 것임을 염두함

내 코드

 class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort()
        res = 0
        prevEnd = intervals[0][1]
        for start, end in intervals[1:]:
            if start >= prevEnd:
                prevEnd = end
            else:
                res += 1
                prevEnd = min(end, prevEnd)
        return res

증빙

여담

아싸 난 내일 회사안감 ㅋ