Leetcode: Intervals

Question 1

435. Non-overlapping Intervals

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.

Example 1:

Input: intervals = [[1,2],[2,3],[3,4],[1,3]]
Output: 1
Explanation: [1,3] can be removed and the rest of the intervals are non-overlapping.
Example 2:

Input: intervals = [[1,2],[1,2],[1,2]]
Output: 2
Explanation: You need to remove two [1,2] to make the rest of the intervals non-overlapping.

Answer 1

A classic greedy case: interval scheduling problem.

The heuristic is: always pick the interval with the earliest end time. Then you can get the maximal number of non-overlapping intervals. (or minimal number to remove).
This is because, the interval with the earliest end time produces the maximal capacity to hold rest intervals.
E.g. Suppose current earliest end time of the rest intervals is x. Then available time slot left for other intervals is [x:]. If we choose another interval with end time y, then available time slot would be [y:]. Since x ≤ y, there is no way [y:] can hold more intervals then [x:]. Thus, the heuristic holds.

Therefore, we can sort interval by ending time and key track of current earliest end time. Once next interval’s start time is earlier than current end time, then we have to remove one interval. Otherwise, we update earliest end time.

time: O(n logn) for sorting the array, then N to iterate
space: O(n) bc standard python sorting takes N space, we also copy the interval array. we could implement QS to get log(n) space

class Solution:

• —def eraseOverlapIntervals(self, intervals):
• ——-if len(intervals) < 2:
• ———–return 0
• ——-intervals.sort(key=lambda x:x[1])
• ——-end = intervals[0][1]
• ——-count = 1
• ——-for i in range(count, len(intervals)):
• ———–if intervals[i][0] >= end:
• —————end = intervals[i][1]
• —————count += 1
• ——-return len(intervals) - count

Question 2

252. Meeting Rooms

Given an array of meeting time intervals where intervals[i] = [starti, endi], determine if a person could attend all meetings.

Example 1:

Input: intervals = [[0,30],[5,10],[15,20]]
Output: false
Example 2:

Input: intervals = [[7,10],[2,4]]
Output: true

Answer 2

A classic greedy case: interval scheduling problem.

The heuristic is: always pick the interval with the earliest end time. Then you can get the maximal number of non-overlapping intervals. (or minimal number to remove).
This is because, the interval with the earliest end time produces the maximal capacity to hold rest intervals.
E.g. Suppose current earliest end time of the rest intervals is x. Then available time slot left for other intervals is [x:]. If we choose another interval with end time y, then available time slot would be [y:]. Since x ≤ y, there is no way [y:] can hold more intervals then [x:]. Thus, the heuristic holds.

Therefore, we can sort interval by ending time and key track of current earliest end time. Once next interval’s start time is earlier than current end time, then we have to remove one interval. Otherwise, we update earliest end time.

1. all interval problems, sort based on the end key!
2. for 1 -> len(intervals), check if previous end <= current start. if it is, we good, set the new end to the current one! otherwise it is not valid

time: O(n logn), sorted takes that time
space: O(n), sorted takes N space in python, but quick sort could take log n time.

class Solution:

• —def canAttendMeetings(self, intervals):
• ——-if len(intervals) < 2:
• ———–return True
• ——-intervals.sort(key=lambda x: x[1])
• ——-end = intervals[0][1]
• ——-for i in range(1, len(intervals)):
• ———–if intervals[i][0] < end:
• —————return False
• ———–end = intervals[i][1]
• ——-return True

Question 3

253. Meeting Rooms II

Given an array of meeting time intervals intervals where intervals[i] = [starti, endi], return the minimum number of conference rooms required.

Example 1:

Input: intervals = [[0,30],[5,10],[15,20]]
Output: 2
Example 2:

Input: intervals = [[7,10],[2,4]]
Output: 1

Answer 3

5 15, 10 15, 15 25, 16 27 is the edge case that we cant use the same logic as non-overlapping-intervals. it evaluates 3 rooms (bc we start at 1 room, and would have 2 that mee the bad conditions, making it 3 total rooms, answer is 2)

1. priority queue! heapq
2. sort the intervals based on start time
3. add end time to heap, check end <= next start time. If so, heap.pop()
4. if it is not, heap.push the new end value
5. this helps us dynamically remove meeting times that are “over” bc the start time for the next meeting is after the end time of the smallest item on the queue, which is the “pop” item.
6. at the end, we return length of needed rooms

time: O(n log N) for sorting, then N for iteration
space: O(n), sorting can take N time and the heap is N

import heapq
class Solution:
—-def minMeetingRooms(self, intervals):
——–if not len(intervals):
————return 0
——–
——–rooms = []
——–intervals.sort()
——–
——–heapq.heappush(rooms, intervals[0][1])
——–
——–for i in range(1, len(intervals)):
————if rooms[0] <= intervals[i][0]:
—————-heapq.heappop(rooms)
————
————heapq.heappush(rooms, intervals[i][1])
——–
——–return len(rooms)

1. given [[13,15],[1,13],[6,9]], sort the start/end times in different arrays
   1 6 13
   9 13 15
2. iterate over the start array, each iteration has the option to add a new room, but each iteration also has the chance to remove a room from contention
3. for 1 and 6, start < end time, so we need 2 rooms, but for 13, we go neutral bc we add 13 and “remove” a previous room from the count, we can do this bc 13 >= 9, so the meeting at 9 has ended
4. LC does a good job explaining this too

time: O(n log N) for sorting, then N for iteration
space: O(n), sorting can take N time and the heap is N

• —def optimal_cronological_order(self, intervals):
• ——-start = sorted([x[0] for x in intervals])
• ——-end = sorted([x[1] for x in intervals])
• ——-spointer = endpointer = rooms = 0—-
• ——-for spointer in range(len(intervals)):
• ———–if start[spointer] >= end[endpointer]:
• —————rooms -= 1
• —————endpointer += 1
• ———–rooms += 1
• ——-return rooms

Question 4

56. Merge Intervals

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] overlaps, merge them into [1,6].
Example 2:

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

Answer 4

non-overlapping intervals method has an interesting heuristic that only finds the “bad” intervals, it has no good way of using that information for anything else

1. sort based on 0 index
2. prime the output with the first index, keep track of the index in the output and the end value
3. each iteration 1, len, if end < start, we have a new valid interval, so we add those values to the arr and incrememnt the index
4. each iteration we check for a new higher end value and update the current out-index value. if they are the same nothing changes
5. if end >= start, then we just update the end value in the output, it will have the previous out value bc of the outindex

time: O(n log n) to sort, the n to iterate
space: O(n) for python, but we can do sorting in logN time with quick sort or constant with heap

class Solution:
----def merge(self, intervals):
--------if not intervals:
------------return []
--------intervals.sort(key=lambda x: x[0])
--------
--------output = [intervals[0][:]]
--------out_index = 0
--------end = intervals[0][1]
--------
--------for i, interval in enumerate(intervals[1:], start=1):
------------start, end2 = interval
# 1,4 and 4,5 are considered overlapping in this case! why idfk
------------if end < start:
----------------out_index += 1
----------------output.append(intervals[i][:])
------------end = max(end, end2)
------------output[out_index][1] = end
--------return output

Question 4

56. Merge Intervals

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] overlaps, merge them into [1,6].
Example 2:

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

Answer 4

non-overlapping intervals method has an interesting heuristic that only finds the “bad” intervals, it has no good way of using that information for anything else

1. sort based on 0 index
2. prime the output with the first index, keep track of the index in the output and the end value
3. each iteration 1, len, if end < start, we have a new valid interval, so we add those values to the arr and incrememnt the index
4. each iteration we check for a new higher end value and update the current out-index value. if they are the same nothing changes
5. if end >= start, then we just update the end value in the output, it will have the previous out value bc of the outindex

time: O(n log n) to sort, the n to iterate
space: O(n) for python, but we can do sorting in logN time with quick sort or constant with heap

class Solution:
----def merge(self, intervals):
--------if not intervals:
------------return []
--------intervals.sort(key=lambda x: x[0])
--------
--------output = [intervals[0][:]]
--------out_index = 0
--------end = intervals[0][1]
--------
--------for i, interval in enumerate(intervals[1:], start=1):
------------start, end2 = interval
# 1,4 and 4,5 are considered overlapping in this case! why idfk
------------if end < start:
----------------out_index += 1
----------------output.append(intervals[i][:])
------------end = max(end, end2)
------------output[out_index][1] = end
--------return output

Question 5

57. Insert Interval

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]]
Example 2:

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

Answer 5

class Solution:

1. need to find where to start inserting the interval, and when to end
2. find the index where start > newInterval start
3. either add the new interval onto the response or merge it into the response if response[-1][1] >= newInterval start
4. do the same for the rest of the intervals, start range loop at index

time: O(n), it comes sorted. If we had to sort it ourselves, we would have to perform merge interval problem first, then do this
space: O(n), for the response

class Solution:

• —def insert(self, intervals, newInterval):
• ——-start2, end2 = newInterval
• ——-response = []
• ——-index = 0
• ——-while index < len(intervals) and start2 > intervals[index][0]:
• ———–response.append(intervals[index][:])
• ———–index += 1
• ——-if not response or response[index - 1][1] < start2:
• ———–response.append(newInterval)
• ——-else:
• ———–response[-1][1] = max(response[-1][1], end2)
• ——-for i in range(index, len(intervals)):
• ———–if response[-1][1] >= intervals[i][0]:
• —————response[-1][1] = max(response[-1][1], intervals[i][1])
• ———–else:
• —————response.append(intervals[i][:])

——–return response