17. Intervals

A. General Introduction

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

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

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