I'm trying to solve a problem from leetcode, https://leetcode.com/problems/non-overlapping-intervals/

The solution to me seemed pretty simple.

1. sort the intervals by their starting points
2. use two indices. one for previous interval, one for current
3. initially set previous to 0 and current to 1
4. check if previous and current intervals overlap
5. if they do, find the longest interval and remove it
6. Here is how to remove an interval: if previous interval is longer then the current, then set previous index to the current index and move current index to the next position. If current interval is longer than a previous one then move current index to the next position
7. if intervals don't intersect then move set previous index to current index and move current index to the next position

Here is how I implemented it in Python

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        L = len(intervals)
        if L <= 1:
            return 0
        
        intervals.sort(key = lambda x: (x[0], x[1]))
        prev_idx = 0
        curr_idx = 1
        interval_cnt = 0
        while curr_idx < L:
            # intervals intersect
            if intervals[curr_idx][0] < intervals[prev_idx][1]:
                interval_cnt  = 1
                prev_length = intervals[prev_idx][1] - intervals[prev_idx][0]
                curr_length = intervals[curr_idx][1] - intervals[curr_idx][0]
                # remove previous interval
                if prev_length >= curr_length:
                    prev_idx = curr_idx
                    curr_idx  = 1
                else: # remove current interval
                    curr_idx  = 1
            else: # intervals don't intersect
                prev_idx = curr_idx
                curr_idx  = 1
               
        return interval_cnt

When I run my code on the following test case [[-73,-26],[-65,-11],[-63,2],[-62,-49],[-52,31],[-40,-26],[-31,49],[30,47],[58,95],[66,98],[82,97],[95,99]] I get an answer of 8. I also ran the test case manually (i.e. on paper) using the logic from the algorithm and got the answer of 8. However the correct answer is 7.

I did look at the solution for the problem but I can't make heads or tails of it.

Unfortunately I can't post leetcode solution because it is restricted content.

CodePudding user response：

One solution:

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort()
        result = 0
        
        (_, p_end), *intervals = intervals
        for c_start, c_end in intervals:
            if c_start < p_end: # overlap!
                result  = 1
                p_end = min(c_end, p_end)
            else:
                p_end = c_end
        
        return result

1. sort the intervals

2. keep track of the previous interval end p_end

3. for every current interval c_start, c_end

   a. if overlap with previous interval (c_start < p_end)

   1. increment removal count (one of them has to go!)
   2. set the end of previous interval to the smaller end! (remove the interval that ends later, leaving more space for later intervals)

   b. if no overlap

   1. set previous end to current end

Thinking about it, it is even sufficient to sort the intervals by their end. Then we never have to update the p_end in case of an overlap:

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=itemgetter(1))
        result = 0
        (_, p_end), *intervals = intervals
        for c_start, c_end in intervals:
            if c_start < p_end: # overlap!
                result  = 1  # no p_end update needed bcs of the sort!
            else:
                p_end = c_end
        return result

CodePudding user response：

Same idea as earlier PO - sort the ending times to start working...and check the overlapping and increment counts.

Always pick the interval with the earliest end time. Then you can get the maximal number of non-overlapping intervals (or minimal number to remove). This is because, the interval with the earliest end time produces the maximal capacity to hold rest intervals.

Then we just keep track of current earliest end time. Once next interval's start time is earlier than current end time, then we have to remove one interval. Otherwise, we update earliest end time.

Just for another reference.

 def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
     intervals.sort(key=lambda A: A[1])
     overlap = 0
     prev_end = float('-inf')
        
     if len(intervals) <= 1:  return 0
        
     for start, end in intervals:
         if prev_end <= start:
            prev_end = end
         else:
             overlap  = 1
     return overlap