⚡Flashcard Drill➔
NeetCode #846LC-3169MediumIntervals
← Back to All Problems

#846 · #3169 · Count Days Without Meetings(无需开会的工作日)

📌 Problem Statement & Constraints

You are given a positive integer days representing a 1-indexed schedule of days days, and an array meetings where meetings[i] = [start_i, end_i] is a busy interval. Return the number of days with no meetings. Constraints: 1 <= days <= 10^9, 1 <= meetings.length <= 10^5, 1 <= start_i <= end_i <= days.

💡 Core Algorithmic Approaches

  1. The busy days are the union of the meeting intervals, which can be computed by merging overlapping intervals.
  2. Sort the meetings by start, then merge while the next start is at most the current end plus one (adjacent or overlapping intervals merge into one busy block).
  3. Sum the lengths of the merged blocks and subtract from days.
  4. Merging first is essential because overlapping meetings would otherwise be double-counted.

💻 Benchmark Python3 Implementation

class Solution:
    def countDays(self, days: int, meetings: List[List[int]]) -> int:
        meetings.sort()
        busy = 0
        cur_start, cur_end = meetings[0]
        for s, e in meetings[1:]:
            if s <= cur_end + 1:                # overlapping or adjacent -> merge
                cur_end = max(cur_end, e)
            else:
                busy += cur_end - cur_start + 1
                cur_start, cur_end = s, e
        busy += cur_end - cur_start + 1
        return days - busy

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n log n): the sort dominates.
💾 Space Complexity
O(1) beyond the sort.

⚠️ Interview Pitfalls & Follow-ups

  • Merging only when s <= cur_end: adjacent blocks like [1,2] and [3,4] cover 1-4 contiguously, so the test includes cur_end + 1.
  • Double-counting overlapping meetings: merging first collapses them into one block.
  • Forgetting the final block: the loop only flushes a block when a gap is found, so the last block is added after the loop.
  • Assuming meetings may be empty: the constraints guarantee at least one meeting, so indexing meetings[0] is safe.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Intervals Problems