Consolidating Calendar Blocks

TIP103 Unit 11 Session 2 (Click for link to problem statements)

Consolidating Calendar Blocks

A calendar holds busy blocks as [start, end] pairs in intervals. Overlapping or touching blocks should be merged into single blocks.

Return the merged list of non-overlapping intervals.

def merge(intervals):
    pass

Problem Highlights

• 💡 Difficulty: Medium
• ⏰ Time to complete: 20-30 mins
• 🛠️ Topics: Intervals, Sorting, Merge Intervals

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Established a set (2-3) of test cases to verify their own solution later.
• Established a set (1-2) of edge cases to verify their solution handles complexities.
• Have fully understood the problem and have no clarifying questions.
• Have you verified any Time/Space Constraints for this problem?

• Q: What does it mean for two blocks to overlap or touch?

  • A: Blocks [a, b] and [c, d] overlap when they share time (c < b), and they touch when one ends exactly where the other starts (c == b). Both cases should be consolidated into a single block, so [1, 4] and [4, 5] become [1, 5].

• Q: Is the input guaranteed to be sorted by start time?

  • A: No. We should not assume any ordering, so sorting the blocks by start time first makes overlap detection straightforward.

• Q: What should be returned for an empty calendar?

  • A: An empty list — there are no busy blocks to merge.

HAPPY CASE
Input: intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
Output: [[1, 6], [8, 10], [15, 18]]
Explanation: [1, 3] and [2, 6] overlap, so they merge into [1, 6]. The other blocks do not overlap or touch anything.

Input: intervals = [[1, 4], [4, 5]]
Output: [[1, 5]]
Explanation: [1, 4] and [4, 5] touch at time 4, so they merge into a single block [1, 5].

EDGE CASE
Input: intervals = [[5, 7]]
Output: [[5, 7]]
Explanation: A single block has nothing to merge with, so it is returned as is.

Input: intervals = [[1, 10], [2, 3], [4, 5]]
Output: [[1, 10]]
Explanation: [2, 3] and [4, 5] are fully contained inside [1, 10], so everything collapses into one block.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Interval Problems, we can consider the following approaches:

• Merge Intervals Pattern: Sort the intervals by start time, then sweep through them once, extending the current block whenever the next block overlaps or touches it.
• Sorting: Ordering by start time guarantees that any block which can merge with the current one appears immediately after it, so a single pass suffices.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Sort the busy blocks by start time. Keep a merged list whose last entry is the block currently being built. For each subsequent block, if its start is less than or equal to the end of the last merged block, the two overlap or touch — extend the last block's end to the larger of the two ends. Otherwise there is a gap, so append the block as a new entry.

1) If `intervals` is empty, return an empty list.
2) Sort `intervals` by start time.
3) Initialize `merged` with the first block.
4) For each remaining block `[start, end]`:
   a) If `start` <= end of the last block in `merged`, the blocks overlap or touch:
      set the last block's end to max(last end, `end`).
   b) Otherwise, append `[start, end]` to `merged` as a new block.
5) Return `merged`.

⚠️ Common Mistakes

• Using start < last_end instead of start <= last_end, which misses touching blocks like [1, 4] and [4, 5].
• Forgetting to take max(last_end, end) when extending, which breaks when a block is fully contained inside the previous one (e.g. [1, 10] followed by [2, 3]).
• Comparing blocks without sorting first, which misses merges between blocks that are far apart in the original list.

4: I-mplement

Implement the code to solve the algorithm.

def merge(intervals):
    if not intervals:
        return []

    # Sort blocks by start time so mergeable blocks are adjacent
    intervals.sort(key=lambda block: block[0])

    merged = [intervals[0]]
    for start, end in intervals[1:]:
        last = merged[-1]
        if start <= last[1]:
            # Overlaps or touches the last merged block; extend it
            last[1] = max(last[1], end)
        else:
            # Gap before this block; start a new merged block
            merged.append([start, end])

    return merged

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

• Input: intervals = 1, 3], [2, 6], [8, 10], [15, 18

  • After sorting: 1, 3], [2, 6], [8, 10], [15, 18. Start merged = [[1, 3]].
  • [2, 6]: 2 <= 3, so extend the last block to [1, 6]. merged = [[1, 6]].
  • [8, 10]: 8 > 6, so append. merged = [[1, 6], [8, 10]].
  • [15, 18]: 15 > 10, so append. merged = [[1, 6], [8, 10], [15, 18]].
  • Output: 1, 6], [8, 10], [15, 18

• Input: intervals = 1, 4], [4, 5

  • Start merged = [[1, 4]].
  • [4, 5]: 4 <= 4 (touching), so extend the last block to [1, 5]. merged = [[1, 5]].
  • Output: 1, 5

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N is the number of busy blocks in intervals.

• Time Complexity: O(N log N) because sorting the blocks dominates; the merging sweep itself is a single O(N) pass.
• Space Complexity: O(N) for the merged output list (or O(log N) to O(N) auxiliary space for sorting, depending on the sort implementation).