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:

You may assume the interval's end point is always bigger than its start point.
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.

Difficulty: interview

Starter code:

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

Solutions:
# Definition for an interval.
 # class Interval:
 #     def __init__(self, s=0, e=0):
 #         self.start = s
 #         self.end = e
 
 class Solution:
     def eraseOverlapIntervals(self, intervals):
         """
         :type intervals: List[Interval]
         :rtype: int
         """
         intervals = sorted(intervals, key = lambda x: x.end)
         current_end = float('-inf')
         cnt = 0
         for interval in intervals:
             if interval.start >= current_end:
                 cnt += 1
                 current_end = interval.end
         return len(intervals) - cnt
         

# Definition for an interval.
 # class Interval:
 #     def __init__(self, s=0, e=0):
 #         self.start = s
 #         self.end = e
 
 class Solution:
     def eraseOverlapIntervals(self, intervals):
         """
         :type intervals: List[Interval]
         :rtype: int
         """        
         intervals.sort(key=lambda x: (x.start, x.end))
         
         num_removed = 0
         current_interval_end = float('-inf')      
         for interval in intervals:
             if interval.start >= current_interval_end:
                 # No overlap
                 current_interval_end = interval.end
             else:
                 # Overlapping intervals. Remove interval with latest end time
                 current_interval_end = min(current_interval_end, interval.end)
                 num_removed += 1
         return num_removed

# Definition for an interval.
 # class Interval:
 #     def __init__(self, s=0, e=0):
 #         self.start = s
 #         self.end = e
 
 class Solution:
     def eraseOverlapIntervals(self, intervals):
         """
         :type intervals: List[Interval]
         :rtype: int
         """
         if len(intervals) <= 1: return 0
         min_removals = 0
         j = 1
         intervals = sorted(intervals, key=lambda i: (i.start, i.end))
         endpoint = intervals[0].end
         
         while j < len(intervals):
             if intervals[j].start < endpoint:
                 min_removals+=1
                 endpoint = min(endpoint, intervals[j].end)
             else:
                 endpoint = intervals[j].end
             j+=1
         
         return min_removals
         
         
             

# Definition for an interval.
 # class Interval:
 #     def __init__(self, s=0, e=0):
 #         self.start = s
 #         self.end = e
 
 class Solution:
     def eraseOverlapIntervals(self, intervals):
         """
         :type intervals: List[Interval]
         :rtype: int
         """
         s_intervals = [(intervals[i].start, intervals[i].end) for i in range(len(intervals))]
         s_intervals.sort()
         s_intervals = [(s_intervals[i][0], s_intervals[i][1], i) for i in range(len(intervals))]
         f_intervals = [(j,i,h) for (i,j,h) in s_intervals]
         f_intervals.sort()
         f_intervals = [(j,i,h) for (i,j,h) in f_intervals]
         
         skipped = 0
         bound = 0
         for interval in f_intervals:
             if interval[2] < bound:
                 continue
             i = bound
             for i in range(bound, len(intervals)):
                 if s_intervals[i][2] == interval[2]:
                     continue
                 if s_intervals[i][0] >= interval[1]:
                     break
                 else:
                     skipped += 1
             bound = i
         return skipped
                 

# Definition for an interval.
 # class Interval:
 #     def __init__(self, s=0, e=0):
 #         self.start = s
 #         self.end = e
 
 class Solution:
     def eraseOverlapIntervals(self, intervals):
         """
         :type intervals: List[Interval]
         :rtype: int
         """
         start_end={}
         for i in intervals:
             if i.start in start_end:
                 if start_end[i.start]>i.end:
                     start_end[i.start]=i.end
             else:
                 start_end[i.start]=i.end
         final_list={}
         if len(start_end)>1:
             sorted_list=sorted(start_end)
 
             for i,j in enumerate(sorted_list):
                 if i>0:
                     start2=j
                     #if j>-90 and j<-80:
                     #    print(start1,end1,start2,start_end[start2])
                     if start2<end1:
                         if start_end[start2]<end1:
                             final_list.pop(start1,None)
                             end2=start_end[start2]
                             final_list[start2]=end2
                             end1=end2
                             start1=start2
                             #if j>-90 and j<-80:
                             #    print(start1,end1)
                         elif end1<=start_end[start2]:
                             final_list[start1]=end1
                             end1=end1
                             start1=start1
                             #if j>-90 and j<-80:
                             #    print(start1,end1)
                     elif start2>=end1:
                         final_list[start1]=end1
                         start1=start2
                         end1=start_end[start2]
                         if i==len(sorted_list)-1:
                             final_list[start2]=start_end[start2]
                 if i==0:
                     start1=j
                     end1 =start_end[j]
         elif len(start_end)==1:
             final_list=start_end
         print(list((i,start_end[i]) for i in sorted(start_end)))
         print('result') 
         print(list((i,final_list[i]) for i in sorted(final_list)))
         return len(intervals)-len(final_list)
                 
                 
                 

# Definition for an interval.
 # class Interval:
 #     def __init__(self, s=0, e=0):
 #         self.start = s
 #         self.end = e
 
 class Solution:
     def eraseOverlapIntervals(self, intervals):
         """
         :type intervals: List[Interval]
         :rtype: int
         """
         if len(intervals) == 0:
             return 0
         
         intervals = sorted(intervals, key = lambda x: (x.end, -x.start))
         
         end = intervals[0].end
         
         res = 0
         
         for interval in intervals[1:]:
             
             if end > interval.start:
                 res += 1
             else:
                 end = interval.end
         
         for i in intervals:
             print((i.start,i.end))
         return res
         
         

# Definition for an interval.
 # class Interval:
 #     def __init__(self, s=0, e=0):
 #         self.start = s
 #         self.end = e
 
 class Solution:
     def eraseOverlapIntervals(self, intervals):
         """
         :type intervals: List[Interval]
         :rtype: int
         """
         if not intervals:
             return 0
         intervals.sort(key=lambda x:x.start) # start or end doesn't matter
         latest = intervals[0].end # always check end 
         count = 0
         for interval in intervals[1:]:
             if interval.start < latest:
                 count += 1
                 latest = min(latest, interval.end)
             else:
                 latest = interval.end
         return count

# Definition for an interval.
 # class Interval:
 #     def __init__(self, s=0, e=0):
 #         self.start = s
 #         self.end = e
 
 class Solution:
     def eraseOverlapIntervals(self, intervals):
         if not intervals: return 0
         intervals = sorted(intervals, key=lambda x: x.end)
         prev_end = intervals[0].end
         count = 0
         for i in intervals[1:]:
             if i.start < prev_end:
                 count += 1
             else:
                 prev_end = i.end
         return count

class Solution:
     def eraseOverlapIntervals(self, intervals):
         intervals.sort(key=lambda x:x.end)        
         end = -sys.maxsize
         count = 0
         for i in intervals:
             if i.start<end: continue
             end = i.end
             count += 1
         return len(intervals)-count

# Definition for an interval.
 # class Interval:
 #     def __init__(self, s=0, e=0):
 #         self.start = s
 #         self.end = e
 
 class Solution:
     def eraseOverlapIntervals(self, intervals):
         """
         :type intervals: List[Interval]
         :rtype: int
         """
         if not intervals:
             return 0
         intervals = sorted(intervals, key= lambda x:x.end)
         count = 1;
         last = 0;
         for i in range(1,len(intervals)):
             if intervals[last].end <= intervals[i].start:
                 count +=1
                 last = i;
         
         return len(intervals) - count