Skip to content

Merge Calendar Intervals

Level: L3-L4 Topics: Intervals, Sorting, Merging

Problem Statement

You are given a list of meetings, each represented as a (start, end) interval, and a single "Do Not Schedule" (DNS) time slot. Your task is to:

  1. Merge all overlapping meetings into non-overlapping intervals.
  2. Apply the DNS slot by cutting any merged meeting that overlaps with it. Meetings that fall entirely within the DNS window are removed. Meetings that partially overlap are trimmed so that no meeting time falls inside the DNS window.

Return the final list of non-overlapping meeting intervals.

Background & Constraints

  • Meeting intervals are given as pairs of integers representing time units (e.g., hours in a day).
  • Meetings may overlap with each other and with the DNS slot.
  • The DNS slot represents a protected block where no meetings are allowed.
  • The output should contain no overlapping intervals and no time that falls within the DNS window.
  • Intervals are inclusive of their start and exclusive of their end, or as clarified by the interviewer.

Examples

Input:

  • Meetings: [(1,7), (5,10), (12,30), (22,30), (40,50), (60,70)]
  • DNS slot: (18, 25)

Step 1 — Merge overlapping meetings:

[(1,7), (5,10)] merge into (1,10). [(12,30), (22,30)] merge into (12,30).

After merging: [(1,10), (12,30), (40,50), (60,70)]

Step 2 — Apply DNS (18, 25):

The interval (12,30) overlaps with DNS (18,25). Split it into (12,18) and (25,30).

Output: [(1,10), (12,18), (25,30), (40,50), (60,70)]

Hints & Common Pitfalls

  • Start by solving the classic "merge overlapping intervals" problem before adding the DNS logic.
  • Sort meetings by start time before merging.
  • When applying the DNS slot, consider three cases for each merged interval: entirely before DNS, entirely after DNS, or overlapping (which requires splitting).
  • Be careful with edge cases where DNS exactly aligns with a meeting boundary.
  • A common mistake is applying DNS before merging, which can produce incorrect results if unmerged meetings span across the DNS boundary.

Follow-Up Questions

  1. Multiple DNS slots: How would you handle multiple DNS windows? Consider that DNS slots themselves may overlap and should be merged first. Then apply them in order against the merged meetings.
  2. Meetings with importance levels: Each meeting has a priority score. When two meetings overlap, the one with the higher priority keeps its full time and the lower-priority meeting is trimmed. How does this change your approach?