#132 Medium Time O(n log n) Space O(1) Animated

Non-overlapping Intervals

Find minimum intervals to remove so rest are non-overlapping.

LeetCode ↗

Approach: Greedy (Sort by End Time)

Click play to start

Step 0 / 0

Press play to start the visualization.

1×

Description

Find minimum intervals to remove so rest are non-overlapping.

Constraints

Time Complexity: O(n log n)
Space Complexity: O(1)

Solution — Greedy (Sort by End Time)

O(n log n) O(1)

def eraseOverlapIntervals(intervals):
    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

Merge Intervals

Meeting Rooms

Non-overlapping Intervals

Steps

Description

Constraints

Tags

Solution — Greedy (Sort by End Time)