435. Non-overlapping Intervals

Description

See: https://leetcode.com/problems/non-overlapping-intervals/

Notes

input	expected output
[[3,4],[1,4]]	1
[[3,4],[1,3]]	0
[[6,10], [5,7], [7,9]]	1
[[6,10], [5,7], [7,9], [8,11]]	2
[[5, 20], [7, 10]]	1
[[6,10], [7,9]]	1
[[1,2],[1,2],[1,2],[2,7],[2,9]]	3
[[1,20], [3, 5], [7,10], [12, 15]]	1

Example of overlapping intervals (number 3 in above table)

Strategy

• Sort the array. This makes it easy to compare intervals to see if two intervals overlap. Why? Because, potentially overlapping intervals will be next to each other in a sorted array. If the array is not sorted we would have to compare an interval against all the other intervals to see if they overlap.

• Given two intervals: [start1, end1] and [start2, end2]

  • intervals overlap if: start1 <= start2 < end1

    • However, since the array is sorted we do NOT need to do the start1 <= start2 check. The array is sorted so we are guaranteed that start1 <= start2. We just need to check that start2 < end1.

• To decide which interval to discard we keep track of the end value. Which end value is used depends on whether we are in an overlap or not.

  • If start2 < end1 (in an overlap)

    • end = min(end, end2)

    • Here the minimum of the previous end and the 2nd end is used. Why? Because we want to find the minimum number of intervals to discard. An interval with a higher end point will span additional numbers, which means there could potentially be more intervals to come that would fall in that range. So, by eliminating that end point we are getting the minimum number of intervals to remove.

  • Otherwise we are not in an overlap (start2 >= end1):

    • end = end2

    • Why? Because there is not an overlap, so we do not want to keep track of the previous end. It is no longer of concern. The 2nd end is used, because that value will be compared against the next interval in the list.

Solution

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

Time complexity: O(n log n). The time complexity is from sorting the array.

Space complexity: O(1). This is because the array is sorted in place, but it means the input array is modified. If the input array is not allowed to be modified then a seperate sorted array would need to be created and the space complexity would be O(n).

Take-away

Drawing pictures really helped in this situation.