commit f0d10bbd1ce2281b7abfaa4e6af28590027c977d parent b2340319622126515c448a1e4c6f06ef5f0aa2e6 Author: Andrew Laack <andrew@laack.co> Date: Mon, 14 Jul 2025 08:37:56 -0500 Completed non overlapping intervals Diffstat:
| A | non-overlapping-intervals/non-overlapping-intervalsV2.py | | | 60 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
1 file changed, 60 insertions(+), 0 deletions(-)
diff --git a/non-overlapping-intervals/non-overlapping-intervalsV2.py b/non-overlapping-intervals/non-overlapping-intervalsV2.py @@ -0,0 +1,60 @@ +# INTUITION: + +# merge intervals to ensure they are non-overlapping +# return difference in list size from start to merged list + +# LESS MEMORY? +# SMALL CONSTANT FACTORS? + +# we might be able to use constant memory by doing our upper and lower comparisons in place + +# APPROACH + +# 1) Sort list by start ascending +# 2) Perform pseudo-merge (this can allow less memory usage than true) +# a) loop through each element +# i) if lower > uppermost found: +# set uppermost found +# don't increment infraction counter +# ii) if lower < uppermost found: +# set uppermost found to be max(prior, current_upper) +# increment infraction counter +# 3) Return infraction counter + +# PROBLEM W/ APPROACH: + +# This may not be the optimal removal approach +# instead of above we could try removing the interval with the highest +# max at each infraction step. + +# === + +# as we go track all uppers that we've found, in a heap +# pop the heap whenever we need to remvoe an interval to ensure this works correctly +# we then check to see if there are other elements invalidating the current one +# if there are we remove them as well. +# we then insert the current upper and continue. + +# TC: +# nlogn - sort +# nlogn - worst case at a step +# logn - ac for step + +# WCATC - nlogn + + +class Solution: + def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int: + + intervals.sort(key=lambda x: x[-1]) + removed = 0 + upper = -100000 + + for interval in intervals: + if interval[0] < upper: + removed += 1 + continue + + upper = interval[1] + + return removed