Leetcode week #8: Intervals

Aug 19, 2024 | monday 7:00 pm

This series will be mainly focused for my own accountability and reference, as well as anyone who wants to follow my journey to becoming a better problem solver. Each week, I will highlight problems that I thought was interesting or difficult. Additionally, other problems that I solved and their solutions are listed below.

1. 🔴 Minimum Interval to Include Each Query
2. 🟢 Meeting Rooms
3. 🟡 Insert Intervals
4. 🟡 Merge Intervals
5. 🟡 Non Overlapping Intervals
6. 🟡 Meeting Rooms II

Minimum Interval to Include Each Query

HardIntervals

Try it yourself here!

Problem Statement: Find the smallest interval from a given list of intervals that includes each query number from a list of queries.

Edge Cases:

1. No suitable interval exists for a query (return -1)
2. Queries may be unsorted
3. All intervals could be relevant before processing any queries
4. All queries could be processed before considering any intervals

Solution:

Drawing from experience with interval problems, the general strategy is to sort the interval array first. This approach facilitates left-to-right processing, eliminating concerns about earlier intervals appearing later in the array. Without sorting, most interval problems, including this one, would typically require a brute force algorithm with O(n^2) time complexity. Our goal is to achieve a more efficient O(n log n) solution, where n is the number of intervals.

Key Steps:

Sort both the intervals and queries arrays Use a map to track the minimal interval for each query, preserving the original query order Employ a min heap to efficiently store and retrieve the smallest interval lengths and their endpoints Iterate through the sorted queries:

Add all intervals that start before or at the current query Remove intervals from the heap that end before the current query Add the query and its corresponding minimal interval length to the map

Construct the result array using the original query order and the corresponding minimal interval lengths from the map

Algorithm Details:

1. Sort the intervals based on their start times and the queries in ascending order
2. Initialize a min heap to store interval lengths and endpoints, and a map to store query results
3. For each sorted query:
   • Add all intervals starting before or at the query to the min heap
   • Remove intervals from the heap that end before the query
   • If the heap is not empty, add the query and the smallest interval length to the map
4. Construct the final result array using the original query order and the map

Complexity:

• Time: O(n log n), leverages sorting and a min heap to achieve O(n log n) time complexity, improving upon the brute force O(n^2) solution.

• Space: O(n), At most the heap will store n intervals.

def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:
    intervals.sort()
    i = 0
    res = {}
    heap = []
    for q in sorted(queries):
        while i < len(intervals) and q >= intervals[i][0]:
            l, r = intervals[i]
            heappush(heap, (r - l + 1, r))
            i += 1
        while heap and heap[0][1] < q:
            heappop(heap)
        res[q] = heap[0][0] if heap else -1
    return [res[q] for q in queries]

Meeting Rooms

EasyIntervals

Try it yourself here!

def canAttendMeetings(self, intervals: List[List[int]]) -> bool:
        intervals.sort()
        for i in range(1, len(intervals)):
            if intervals[i][0] < intervals[i - 1][1]:
                return False
        return True

Complexity:

• Time: O(n log n), after sorting.
• Space: O(1).

Insert Intervals

MediumIntervals

Try it yourself here!

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

Complexity:

• Time: O(n), One traversal through intervals.
• Space: O(1), only the result space allocated is used.

Merge Intervals

MediumIntervals

Try it yourself here!

def merge(self, intervals: List[List[int]]) -> List[List[int]]:
    res = []
    intervals.sort(key= lambda x: x[0])

    for start, end in intervals:
        if not res or res[-1][1] < start:
            res.append([start, end])
        else:
            res[-1][1] = max(res[-1][1], end)
    return res

Complexity:

• Time: O(n log n), after sorting.
• Space: O(1).

Non-overlapping Intervals

MediumIntervals

Try it yourself here!

def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
    intervals.sort(key=lambda x: x[0])
    ans = 0
    prev_end = intervals[0][1]
    for start, end in intervals[1:]:
        if prev_end <= start:
            prev_end = end
        else:
            ans += 1
            prev_end = min(end, prev_end)
    return ans

Complexity:

• Time: O(n log n), after sorting.
• Space: O(1).

Meeting Rooms II

MediumIntervals

Try it yourself here!

def minMeetingRooms(self, intervals: List[List[int]]) -> int:
    intervals.sort(key=lambda x: x[0])
    heap = [intervals[0][1]]
    for start, end in intervals[1:]:
        if heap[0] <= start:
            heappop(heap)
        heappush(heap, end)
    return len(heap)

Complexity:

• Time: O(n log n), after sorting.
• Space: O(n), used to store intervals in the heap.