non-overlapping-intervalsV1.py (1648B)
1 # INTUITION: 2 3 # merge intervals to ensure they are non-overlapping 4 # return difference in list size from start to merged list 5 6 # LESS MEMORY? 7 # SMALL CONSTANT FACTORS? 8 9 # we might be able to use constant memory by doing our upper and lower comparisons in place 10 11 # APPROACH 12 13 # 1) Sort list by start ascending 14 # 2) Perform pseudo-merge (this can allow less memory usage than true) 15 # a) loop through each element 16 # i) if lower > uppermost found: 17 # set uppermost found 18 # don't increment infraction counter 19 # ii) if lower < uppermost found: 20 # set uppermost found to be max(prior, current_upper) 21 # increment infraction counter 22 # 3) Return infraction counter 23 24 # PROBLEM W/ APPROACH: 25 26 # This may not be the optimal removal approach 27 # instead of above we could try removing the interval with the highest 28 # max at each infraction step. 29 30 # === 31 32 # as we go track all uppers that we've found, in a heap 33 # pop the heap whenever we need to remvoe an interval to ensure this works correctly 34 # we then check to see if there are other elements invalidating the current one 35 # if there are we remove them as well. 36 # we then insert the current upper and continue. 37 38 # TC: 39 # nlogn - sort 40 # nlogn - worst case at a step 41 # logn - ac for step 42 43 # WCATC - nlogn 44 45 import heapq 46 47 48 class Solution: 49 def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int: 50 51 intervals.sort(key=lambda x: x[-1]) 52 uppers = [] 53 removed = 0 54 55 for interval in intervals: 56 if len(uppers) > 0 and interval[0] < -uppers[0]: 57 removed += 1 58 continue 59 60 heapq.heappush(uppers, -interval[1]) 61 62 return removed