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
- The busy days are the union of the meeting intervals, which can be computed by merging overlapping intervals.
- 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).
- Sum the lengths of the merged blocks and subtract from
days. - 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 includescur_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
meetingsmay be empty: the constraints guarantee at least one meeting, so indexingmeetings[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.