non-overlapping-intervalsV2.py (1596B)
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 46 class Solution: 47 def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int: 48 49 intervals.sort(key=lambda x: x[-1]) 50 removed = 0 51 upper = -100000 52 53 for interval in intervals: 54 if interval[0] < upper: 55 removed += 1 56 continue 57 58 upper = interval[1] 59 60 return removed