Leetcode problem solution (0435): non overlapping interval (Python)

subject ：​ ​ The original title is link ​​（ secondary ）

label ： Greedy Algorithm

solution

Time complexity

Spatial complexity

Execution time

Ans 1 (Python)

O ( N l o g N )

O ( N )

84ms (77%)

Ans 2 (Python)

Ans 3 (Python)

Solution 1 ：

class Solution:

 def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:

 if not intervals:

 return 0



 intervals.sort(key=lambda x: x[1])



 size = len(intervals)



 now = intervals[0][1]



 ans = size - 1



 for i in range(1, size):

 if intervals[i][0] >= now:

 ans -= 1

 now = intervals[i][1]



 return ans


1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.