Intervals

Question 1

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],…] (si < ei), determine if a person could attend all meetings.

Answer 1

• Sort array.
• Compare end of current to start of next.

intervals.sort(key=lambda i : i.start)

Question 2

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],…] (si < ei), find the minimum number of conference rooms required.)

Answer 2

• It’s asking for the number of meetings that overlap at any given point in time.
• Create two sorted arrays: one for start times and one for end times.
• Iterate through them with two pointers, keeping track of num of concurrent meetings.
• (you don’t need to check for equality case separately)

    start = sorted([i.start for i in intervals])
    end = sorted([i.end for i in intervals])
    count = 0
    maxCount = 0
    i, j = 0, 0
    while i < len(start) and j < len(end):
        if start[i] < end[j]:
            i += 1
            count += 1
        else:
            j += 1
            count -= 1
        maxCount = max(maxCount, count)
    return maxCount

Question 3

You are given an array of non-overlapping intervals intervals where intervals[i] = [starti, endi] represent the start and the end of the ith interval and intervals is sorted in ascending order by starti. You are also given an interval newInterval = [start, end] that represents the start and end of another interval.

Insert newInterval into intervals such that intervals is still sorted in ascending order by starti and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).

Return intervals after the insertion.

Example 1:

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

Answer 3

• Append to a result array instead of inserting into original.
• Loop through the input array, and see what you need to insert at that moment.
• if newInterval comes before current, add new + the rest of the array and return immediately.
• if newInterval comes after the current one, add the current one and keep going
• else it’s overlapping, so update newInterval so it’s a merge of it and current. Take the min of starts and max of ends.

class Solution:
def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
res = []
for i in range(len(intervals)):
if newInterval[1] < intervals[i][0]: # insert new one before
res.append(newInterval)
return res + intervals[i:]
elif newInterval[0] > intervals[i][1]: # insert new one after
res.append(intervals[i])
else:
newInterval = [min(intervals[i][0], newInterval[0]), max(intervals[i][1], newInterval[1])]
res.append(newInterval)
return res

Question 4

What can you draw to visualize interval problems?

Answer 4

a number line and plot the intervals

Question 5

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Example 1:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].

Answer 5

• Sort the input array.
• set a result array, and track current interval
• loop through the input array and check if current interval is overlapping with the next.
• if overlapping, merge them. Keep merging until current is not overlapping with the next.
• After merging, or not merging, append current to result array.

Question 6

Given an array of intervals intervals where intervals[i] = [starti, endi], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

If end time of one is the same as start time of another, they are NOT overlapping.

Answer 6

• sort the intervals
• keep track of the count that you’re removing
• set a previousEnd variable as the end of the first interval.
• Iterate through the remainder of the array:
• If prev and current not overlapping, move on to the next
• Else, increment count and keep the interval that ENDS FIRST.

def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
intervals.sort()
count = 0
prevEnd = intervals[0][1]
for interval in intervals[1:]:
if prevEnd <= interval[0]:
prevEnd = interval[1]
else:
count += 1
prevEnd = min(interval[1], prevEnd)
return count