Intervals

本記事は以下記事の一部です。

NeetCode 150 全問の解き方とポイントまとめ & 感想

Intervalsはわりと解きやすい気がする。

71. Insert New Interval

Problem

You are given an array of non-overlapping intervals intervals where intervals[i] = [start_i, end_i] represents the start and the end time of the ith interval. intervals is initially sorted in ascending order by start_i.

You are given another interval newInterval = [start, end].

Insert newInterval into intervals such that intervals is still sorted in ascending order by start_i and also intervals still does not have any overlapping intervals. You may merge the overlapping intervals if needed.

Return intervals after adding newInterval.

Note: Intervals are non-overlapping if they have no common point. For example, [1,2] and [3,4] are non-overlapping, but [1,2] and [2,3] are overlapping.

Example 1:

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

Output: [[1,6]]

Copy

Example 2:

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

Output: [[1,2],[3,5],[6,7],[9,10]]

Copy

Constraints:

• 0 <= intervals.length <= 1000
• newInterval.length == intervals[i].length == 2
• 0 <= start <= end <= 1000

Solution

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        res = []
        
        for i, interval in enumerate(intervals):
            if newInterval[1] < interval[0]:
                res.append(newInterval)
                return res + intervals[i:]
            elif newInterval[0] <= interval[1]:
                newInterval = [
                    min(interval[0], newInterval[0]),
                    max(interval[1], newInterval[1])
                ]
            else:
                res.append(interval)
        res.append(newInterval)
        
        return res

72. Merge Intervals

Problem

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.

You may return the answer in any order.

Note: Intervals are non-overlapping if they have no common point. For example, [1, 2] and [3, 4] are non-overlapping, but [1, 2] and [2, 3] are overlapping.

Example 1:

Input: intervals = [[1,3],[1,5],[6,7]]

Output: [[1,5],[6,7]]

Copy

Example 2:

Input: intervals = [[1,2],[2,3]]

Output: [[1,3]]

Copy

Constraints:

• 1 <= intervals.length <= 1000
• intervals[i].length == 2
• 0 <= start <= end <= 1000

Solution

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort()
        stack = [intervals[0]]

        for interval in intervals[1:]:
            if stack and interval[0] <= stack[-1][1]:
                top_interval = stack.pop()
                stack.append([
                    min(interval[0], top_interval[0]),
                    max(interval[1], top_interval[1])
                ])
            else:
                stack.append(interval)
        
        return stack

73. Non Overlapping Intervals

Problem

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

Note: Intervals are non-overlapping even if they have a common point. For example, [1, 3] and [2, 4] are overlapping, but [1, 2] and [2, 3] are non-overlapping.

Example 1:

Input: intervals = [[1,2],[2,4],[1,4]]

Output: 1

Copy

Explanation: After [1,4] is removed, the rest of the intervals are non-overlapping.

Example 2:

Input: intervals = [[1,2],[2,4]]

Output: 0

Copy

Constraints:

• 1 <= intervals.length <= 1000
• intervals[i].length == 2
• -1000 <= starti < endi <= 1000

Solution

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort()

        end_val = intervals[0][1]
        count = 0

        for interval in intervals[1:]:
            if interval[0] < end_val:
                end_val = min(interval[1], end_val)
                count += 1
            else:
                end_val = interval[1]
        
        return count

74. Meeting Rooms

Problem

Given an array of meeting time interval objects consisting of start and end times [[start_1,end_1],[start_2,end_2],...] (start_i < end_i), determine if a person could add all meetings to their schedule without any conflicts.

Example 1:

Input: intervals = [(0,30),(5,10),(15,20)]

Output: false

Copy

Explanation:

• (0,30) and (5,10) will conflict
• (0,30) and (15,20) will conflict

Example 2:

Input: intervals = [(5,8),(9,15)]

Output: true

Copy

Note:

• (0,8),(8,10) is not considered a conflict at 8

Constraints:

• 0 <= intervals.length <= 500
• 0 <= intervals[i].start < intervals[i].end <= 1,000,000

Solution

"""
Definition of Interval:
class Interval(object):
    def __init__(self, start, end):
        self.start = start
        self.end = end
"""

class Solution:
    def canAttendMeetings(self, intervals: List[Interval]) -> bool:
        if not intervals:
            return True
        
        intervals.sort(key=lambda x:x.start)

        prev_end = intervals[0].end
        for interval in intervals[1:]:
            if interval.start < prev_end:
                return False
            else:
                prev_end = interval.end
        
        return True

75. Meeting Rooms II

Problem

Given an array of meeting time interval objects consisting of start and end times [[start_1,end_1],[start_2,end_2],...] (start_i < end_i), find the minimum number of days required to schedule all meetings without any conflicts.

Example 1:

Input: intervals = [(0,40),(5,10),(15,20)]

Output: 2

Copy

Explanation:
day1: (0,40)
day2: (5,10),(15,20)

Example 2:

Input: intervals = [(4,9)]

Output: 1

Copy

Note:

• (0,8),(8,10) is not considered a conflict at 8

Constraints:

• 0 <= intervals.length <= 500
• 0 <= intervals[i].start < intervals[i].end <= 1,000,000

Solution

"""
Definition of Interval:
class Interval(object):
    def __init__(self, start, end):
        self.start = start
        self.end = end
"""

class Solution:
    def minMeetingRooms(self, intervals: List[Interval]) -> int:
        starts = []
        ends = []
        for interval in intervals:
            starts.append(interval.start)
            ends.append(interval.end)
        
        starts.sort()
        ends.sort()

        max_count = 0
        count = 0
        start_i = 0
        end_i = 0
        while start_i < len(starts):
            if starts[start_i] < ends[end_i]:
                count += 1
                max_count = max(max_count, count)
                start_i+=1
            else:
                count -= 1
                end_i += 1
        
        return max_count

76. Minimum Interval to Include Each Query

Problem

You are given a 2D integer array intervals, where intervals[i] = [left_i, right_i] represents the ith interval starting at left_i and ending at right_i (inclusive).

You are also given an integer array of query points queries. The result of query[j] is the length of the shortest interval i such that left_i <= queries[j] <= right_i. If no such interval exists, the result of this query is -1.

Return an array output where output[j] is the result of query[j].

Note: The length of an interval is calculated as right_i - left_i + 1.

Example 1:

Input: intervals = [[1,3],[2,3],[3,7],[6,6]], queries = [2,3,1,7,6,8]

Output: [2,2,3,5,1,-1]

Copy

Explanation:

• Query = 2: The interval [2,3] is the smallest one containing 2, it's length is 2.
• Query = 3: The interval [2,3] is the smallest one containing 3, it's length is 2.
• Query = 1: The interval [1,3] is the smallest one containing 1, it's length is 3.
• Query = 7: The interval [3,7] is the smallest one containing 7, it's length is 5.
• Query = 6: The interval [6,6] is the smallest one containing 6, it's length is 1.
• Query = 8: There is no interval containing 8.

Constraints:

• 1 <= intervals.length <= 1000
• 1 <= queries.length <= 1000
• 1 <= left_i <= right_i <= 10000
• 1 <= queries[j] <= 10000

Solution

import heapq

class Solution:
    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:
        intervals.sort()
        min_heap = []
        interval_i = 0
        res = {} # query -> diff

        for query in sorted(queries):
            while (interval_i < len(intervals) and
                intervals[interval_i][0] <= query):
                diff = intervals[interval_i][1] - intervals[interval_i][0] + 1
                heapq.heappush(min_heap, (diff, intervals[interval_i][0], intervals[interval_i][1]))
                interval_i += 1

            while min_heap and min_heap[0][2] < query:
                heapq.heappop(min_heap)
            
            if min_heap:
                res[query] = min_heap[0][0]
            else:
                res[query] = -1
        
        return [res[q] for q in queries]