Merge Intervals - kjingers/Grokking-Notes GitHub Wiki
Merge Intervals
Given a list of intervals, merge intervals that overlap at all.
So, sort based on start. Then iterate intervals 1 thorough end. If interval overlaps with previous (b.start <= a.end
), then adjust end to the later end. Else, add the previous interval to the output and start again with the current one.
from __future__ import print_function
class Interval:
def __init__(self, start, end):
self.start = start
self.end = end
def print_interval(self):
print("[" + str(self.start) + ", " + str(self.end) + "]", end='')
def merge(intervals):
if len(intervals) < 2:
return intervals
merged = []
# Sort intervals based on start
intervals.sort(key=lambda x: x.start)
start = intervals[0].start
end = intervals[0].end
for i in range(len(intervals)):
cur_interval = intervals[i]
if cur_interval.start <= end:
end = max(end, cur_interval.end)
else:
merged.append(Interval(start, end))
start = cur_interval.start
end = cur_interval.end
merged.append(Interval(start, end))
return merged
Insert Interval
I got the correct answer by first inserting the new interval into the liast of intervals based on start. Then merging with the same algo above. I guess I assumed the existing interval ay not have already been merged.
The solution first skips all intervals that end before the new interval starts (go ahead and append them to output). Once we found an overlapping one, we update our new interval to have the minimum start value between the two intervals and maximum end between the two. Keep doing this what the new interval has an end that is greater than the current intervals start.
def insert(intervals, new_interval):
merged = []
#if new_interval.start <= intervales[0].start:
original_len = len(intervals)
for i in range(len(intervals)):
if new_interval[0] <= intervals[i][0]:
intervals.insert(i, new_interval)
break
# New Interval start is greater than all other starts
# So, need to append to end
if original_len == len(intervals):
intervals.append(new_interval)
# Now Merge
start = intervals[0][0]
end = intervals[0][1]
for i in range(len(intervals)):
curr_interval = intervals[i]
if end >= curr_interval[0]:
end = max(end, curr_interval[1])
else:
merged.append([start, end])
start = curr_interval[0]
end = curr_interval[1]
merged.append([start, end])
return merged
Intervals Intersection
We define two booleans to help us determine if a overlaps b (a starts after b) or b overlaps a (b starts after a). If they overlap, we append to the output the intersection range. Then we iterate only a or b, whichever one ends first.
def merge(intervals_a, intervals_b):
result = []
i, j = 0, 0
start = 0
end = 1
while i < len(intervals_a) and j < len(intervals_b):
a_overlaps_b = intervals_a[i][start] >= intervals_b[j][start] and intervals_a[i][start] <= intervals_b[j][end]
b_overlaps_a = intervals_b[j][start] >= intervals_a[i][start] and intervals_b[j][start] <= intervals_a[i][end]
if a_overlaps_b or b_overlaps_a:
result.append([max(intervals_a[i][start], intervals_b[j][start]), min(intervals_a[i][end], intervals_b[j][end])])
if intervals_a[i][end] < intervals_b[j][end]:
i += 1
else:
j += 1
return result
Minimum Meeting Rooms
We need to keep track of the end times for all meetings currently in rooms. As we iterate though the meetings, we remove all meetings in the heap with an end time that's less than or equal to the current meetings start time. Then we push the current meeting. We keep track of the max heap size, as that will be the number of rooms needed.
from heapq import *
class Meeting:
def __init__(self, start, end):
self.start = start
self.end = end
def __lt__(self, other):
return self.end < other.end
def min_meeting_rooms(meetings):
minheap = []
maxrooms = 0
meetings.sort(key=lambda x: x.end)
for meeting in meetings:
while len(minheap) > 0 and minheap[0].end <= meeting.start:
heappop(minheap)
heappush(minheap, meeting)
maxrooms = max(maxrooms, len(minheap))
return maxrooms
Max CPU Load
Very similar to "Minimum Meetings Rooms" above. Except instead of keeping track of the max size of the head, we keep track of the max cpu_load at any given time.
from heapq import *
class job:
def __init__(self, start, end, cpu_load):
self.start = start
self.end = end
self.cpu_load = cpu_load
def __lt__(self, other):
return self.end < other.end
def find_max_cpu_load(jobs):
minHeap = []
maxLoad = 0
curLoad = 0
jobs.sort(key=lambda x: x.start)
for job in jobs:
while len(minHeap) > 0 and minHeap[0].end <= job.start:
stopped = heappop(minHeap)
curLoad -= stopped.cpu_load
heappush(minHeap, job)
curLoad += job.cpu_load
maxLoad = max(maxLoad, curLoad)
return maxLoad
Employee Free Time
Trick problem (leetcode hard). The solution here creates a new EmployeeInterval
class, which contains an interval, along with the employeeIndex and intervalIndex. This is so we can store all this information in the heap. Then When we pop the smalled start time, we know which employee to push the next interval. And also, we can check whether that employee has any more intervals from the schedule to push.
from __future__ import print_function
from heapq import *
class Interval:
def __init__(self, start, end):
self.start = start
self.end = end
def print_interval(self):
print("[" + str(self.start) + ", " + str(self.end) + "]", end='')
class EmployeeInterval:
def __init__(self, interval, employeeIndex, intervalIndex):
self.interval = interval
self.employeeIndex = employeeIndex
self.intervalIndex = intervalIndex
def __lt__(self, other):
return self.interval.start < other.interval.start
def find_employee_free_time(schedule):
result = []
minHeap = []
for i in range(len(schedule)):
heappush(minHeap, EmployeeInterval(schedule[i][0], i, 0))
previousInterval = minHeap[0].interval
while minHeap:
top = heappop(minHeap)
if top.interval.start > previousInterval.end:
result.append(Interval(previousInterval.end, top.interval.start))
previousInterval = top.interval
else:
if top.interval.end > previousInterval.end:
previousInterval = top.interval
if len(schedule[top.employeeIndex]) > top.intervalIndex + 1:
heappush(minHeap, EmployeeInterval(schedule[top.employeeIndex][top.intervalIndex + 1], top.employeeIndex, top.intervalIndex + 1))
return result