# 17. Intervals

## B. Leetcode Problems

### 56. Merge Intervals

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

Example:

Input: [[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].

#### Key Ideas

• Sort the intervals by start time
• Iterate through the intervals and check if the current interval overlaps with the previous interval
• If it does, set the end time of the interval to the max of both end times
• If it does not, add the interval to the result
Code


class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:

intervals.sort(key=lambda x: x[0])
result = [intervals[0]]

for start,end in intervals[1:]:

prev_start, prev_end = result[-1]

if start <= prev_end:
result[-1][1] = max(end, prev_end)
else:
result.append([start, end])

return result



### 919 · Meeting Rooms II

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.)

Example:

Input: [[0, 30],[5, 10],[15, 20]]
Output: 2 Explanation:
We need two meeting rooms The first room can only accept the meeting in the time range [0, 30] The second room can only accept the meeting in the time range [5, 10] and [15, 20]

#### Key Ideas

Code


class Solution:
"""
@param intervals: an array of meeting time intervals
@return: the minimum number of conference rooms required
"""
def min_meeting_rooms(self, intervals: List[Interval]) -> int:

s,e = 0,0
count = 0
result = float("-inf")

starts = [i.start for i in intervals]
ends = [i.end for i in intervals]

starts.sort()
ends.sort()

while s < len(intervals):

if starts[s] < ends[e]:
count += 1
s += 1

result = max(result, count)
else:
e += 1
count -= 1

return result



Previous
Next