Non-overlapping Intervals LeetCode solution in Python

1
# Runtime: 3035 ms (Top 7.53%) | Memory: 52.8 MB (Top 61.18%)
2

3

4
class Solution:
5
    def eraseOverlapIntervals(
6
        self, intervals: List[List[int]]
7
    ) -> int:  # Time: O(nlogn) and Space: O(1)
8
        intervals.sort()
9
        res = 0
10
        prevEnd = intervals[0][1]
11

12
        for start, end in intervals[
13
            1:
14
        ]:  # we will start from 1 as we already had taken 0 as a base value
15
            if (
16
                start >= prevEnd
17
            ):  # Non overlapping when new interval starts after or from the previous one
18
                prevEnd = end  # prev = [2, prevEnd=3] & new = [start=3, end=4], we have a new end now after checking the new non overlapping interval
19
            else:  # Overlapping when new interval starts in between or from the previous one
20
                res += 1  # prev = [1, prevEnd=2] & new = [start=1, end=3] --> we will delete new=[1, 3] & set prev = [1, prevEnd=2]
21
                prevEnd = min(
22
                    end, prevEnd
23
                )  # we will delete on the interval on the basis of whose interval ends last
24

25
        return res