commit b2340319622126515c448a1e4c6f06ef5f0aa2e6
parent 9fa4140dfba7b609151b5fd99c4ae7a0f65ae42f
Author: Andrew Laack <andrew@laack.co>
Date: Mon, 14 Jul 2025 08:35:17 -0500
Completed non overlapping intervals
Diffstat:
2 files changed, 69 insertions(+), 4 deletions(-)
diff --git a/merge-intervals/merge-intervalsV1.py b/merge-intervals/merge-intervalsV1.py
@@ -5,18 +5,19 @@
# TC: O(nlogn)
+
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
-
+
intervals.sort()
merged = []
for i in range(0, len(intervals)):
current = intervals[i]
- if len(intervals) - 1 != i and overlapping(intervals[i], intervals[i+1]):
- current = merge(intervals[i], intervals[i+1])
-
+ if len(intervals) - 1 != i and overlapping(intervals[i], intervals[i + 1]):
+ current = merge(intervals[i], intervals[i + 1])
+
if merged and overlapping(merged[-1], current):
merged[-1] = merge(merged[-1], current)
else:
@@ -24,10 +25,12 @@ class Solution:
return merged
+
# int1[0] <= int2[0]
def overlapping(int1, int2):
if int1[1] >= int2[0]:
return True
+
def merge(int1, int2):
return [min(int1[0], int2[0]), max(int1[1], int2[1])]
diff --git a/non-overlapping-intervals/non-overlapping-intervalsV1.py b/non-overlapping-intervals/non-overlapping-intervalsV1.py
@@ -0,0 +1,62 @@
+# 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
+
+import heapq
+
+
+class Solution:
+ def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
+
+ intervals.sort(key=lambda x: x[-1])
+ uppers = []
+ removed = 0
+
+ for interval in intervals:
+ if len(uppers) > 0 and interval[0] < -uppers[0]:
+ removed += 1
+ continue
+
+ heapq.heappush(uppers, -interval[1])
+
+ return removed
