435.Non-overlapping Intervals

Tags: [sort], [greedy]

Link: https://leetcode.com/problems/non-overlapping-intervals/?tab=Description

Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Note:

1. You may assume the interval's end point is always bigger than its start point.
2. Intervals like [1,2] and [2,3] have borders "touching" but they don't overlap each other.

Example 1:

Input:
 [ [1,2], [2,3], [3,4], [1,3] ]

Output:
 1

Explanation:
 [1,3] can be removed and the rest of intervals are non-overlapping.

Example 2:

Input:
 [ [1,2], [1,2], [1,2] ]

Output:
 2

Explanation:
 You need to remove two [1,2] to make the rest of intervals non-overlapping.

Example 3:

Input:
 [ [1,2], [2,3] ]

Output:
 0

Explanation:
 You don't need to remove any of the intervals since they're already non-overlapping.

Solution: sort

# Definition for an interval.
# class Interval(object):
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

class Solution(object):
    def eraseOverlapIntervals(self, intervals):
        """
        :type intervals: List[Interval]
        :rtype: int
        """
        if not intervals:
            return 0

        intervals = sorted(intervals, cmp=self.compare_intervals)

        end = -sys.maxint - 1
        counter = 0
        for interval in intervals:
            if end <= interval.start:
                end = interval.end
            else:
                counter += 1

        return counter

    @staticmethod
    def compare_intervals(interval_1, interval_2):
        if interval_1.end != interval_2.end:
            return interval_1.end - interval_2.end
        else:
            return -(interval_1.start - interval_2.start)

Revelation:

• The explanation: When we traverse the intervals, for each interval, we should try our best to keep the interval whose end is smaller (if the end equal, we should try to keep the interval whose start is bigger), to leave more 'space' for others. This is the reason, why we sort the intervals by end ASC, and if the intervals' end are equal, we sort the start DESC.
• When we can use brute-force to solve the problem, we can think whether we can use 'greedy' to optimize the solution.

Note:

• Time complexity = O(nlgn), n is the number of the given intervals.

Time Limited Exceeded

# Definition for an interval.
# class Interval(object):
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

class Solution(object):
    def eraseOverlapIntervals(self, intervals):
        """
        :type intervals: List[Interval]
        :rtype: int
        """
        if not intervals:
            return 0

        intervals = sorted(intervals, cmp=self.compare_start)
        removed_interval_index_set = set()
        return self.erase_overlap_intervals_helper(intervals, removed_interval_index_set)

    @staticmethod
    def compare_start(interval_1, interval_2):
        return interval_1.start - interval_2.start

    def erase_overlap_intervals_helper(self, intervals, removed_interval_index_set):
        # base case
        if self.verify_no_overlap(intervals, removed_interval_index_set):
            return len(removed_interval_index_set)

        min_num_of_removed_intervals = (len(intervals) - 1)
        for i in xrange(len(intervals)):
            if i in removed_interval_index_set:
                continue

            removed_interval_index_set.add(i)
            min_num_of_removed_intervals = min(min_num_of_removed_intervals,
                                               self.erase_overlap_intervals_helper(intervals, removed_interval_index_set))
            removed_interval_index_set.remove(i)

        return min_num_of_removed_intervals

    @staticmethod
    def verify_no_overlap(intervals, removed_interval_index_set):
        if not intervals:
            return True

        prev = None
        for i in xrange(len(intervals)):
            if i in removed_interval_index_set:
                continue
            interval = intervals[i]
            if not prev:
                prev = interval
                continue

            if prev.end > interval.start:
                return False

            prev = interval

        return True

Revelation:

• Brute-force: try all possible ways to remove the intervals.

Note:

• Time complexity = O(n * (n - 1) * (n - 2) * (n - 3) * ... * 1) = O(n!), n is the number of the given intervals.