LeetCode 3169: Count Days Without Meetings (Sort + Merge Intervals)
LeetCode 3169IntervalSortingToday we solve LeetCode 3169 - Count Days Without Meetings.
Source: https://leetcode.com/problems/count-days-without-meetings/
English
Problem Summary
You are given an integer days and meeting intervals [start, end] (inclusive). Return how many days in [1, days] are not covered by any meeting.
Key Insight
This is a classic interval union length problem. Sort intervals by start day, merge overlaps/touching parts, sum covered length, then subtract from days.
Algorithm
- Sort meetings by start, then by end.
- Keep current merged interval [l, r].
- If next interval starts after r, finalize previous length and start a new interval.
- Otherwise extend r = max(r, end).
- Finalize last interval and compute days - covered.
Complexity Analysis
Sorting dominates.
Time: O(n log n).
Space: O(1) extra (excluding sort implementation).
Common Pitfalls
- Forgetting intervals are inclusive, length should be r - l + 1.
- Not merging touching/overlapping intervals correctly.
- Missing the final merged interval after loop.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int countDays(int days, int[][] meetings) {
java.util.Arrays.sort(meetings, (a, b) -> {
if (a[0] != b[0]) return a[0] - b[0];
return a[1] - b[1];
});
long covered = 0;
int l = -1, r = -1;
for (int[] m : meetings) {
int s = m[0], e = m[1];
if (l == -1) {
l = s;
r = e;
} else if (s > r) {
covered += (long) (r - l + 1);
l = s;
r = e;
} else {
r = Math.max(r, e);
}
}
if (l != -1) covered += (long) (r - l + 1);
return (int) (days - covered);
}
}func countDays(days int, meetings [][]int) int {
sort.Slice(meetings, func(i, j int) bool {
if meetings[i][0] != meetings[j][0] {
return meetings[i][0] < meetings[j][0]
}
return meetings[i][1] < meetings[j][1]
})
covered := 0
l, r := -1, -1
for _, m := range meetings {
s, e := m[0], m[1]
if l == -1 {
l, r = s, e
} else if s > r {
covered += r - l + 1
l, r = s, e
} else if e > r {
r = e
}
}
if l != -1 {
covered += r - l + 1
}
return days - covered
}class Solution {
public:
int countDays(int days, vector<vector<int>>& meetings) {
sort(meetings.begin(), meetings.end());
long long covered = 0;
int l = -1, r = -1;
for (auto& m : meetings) {
int s = m[0], e = m[1];
if (l == -1) {
l = s;
r = e;
} else if (s > r) {
covered += (r - l + 1);
l = s;
r = e;
} else {
r = max(r, e);
}
}
if (l != -1) covered += (r - l + 1);
return (int)(days - covered);
}
};class Solution:
def countDays(self, days: int, meetings: List[List[int]]) -> int:
meetings.sort()
covered = 0
l = r = -1
for s, e in meetings:
if l == -1:
l, r = s, e
elif s > r:
covered += r - l + 1
l, r = s, e
else:
r = max(r, e)
if l != -1:
covered += r - l + 1
return days - covered/**
* @param {number} days
* @param {number[][]} meetings
* @return {number}
*/
var countDays = function(days, meetings) {
meetings.sort((a, b) => (a[0] - b[0]) || (a[1] - b[1]));
let covered = 0;
let l = -1, r = -1;
for (const [s, e] of meetings) {
if (l === -1) {
l = s;
r = e;
} else if (s > r) {
covered += (r - l + 1);
l = s;
r = e;
} else {
r = Math.max(r, e);
}
}
if (l !== -1) covered += (r - l + 1);
return days - covered;
};中文
题目概述
给定总天数 days 和若干会议区间 [start, end]（闭区间），求区间 [1, days] 中没有任何会议覆盖的天数。
核心思路
本质是先求“所有会议覆盖天数的并集长度”。把区间按起点排序后做合并，最后用 days - covered 得到空闲天数。
算法步骤
- 按起点（再按终点）对 meetings 排序。
- 维护当前合并区间 [l, r]。
- 若新区间起点 s > r，说明与当前区间不相交，先结算 [l, r]，再开启新区间。
- 否则合并：r = max(r, e)。
- 循环结束后别忘了结算最后一段。
复杂度分析
主要开销来自排序。
时间复杂度：O(n log n)。
空间复杂度：O(1)（不计排序内部开销）。
常见陷阱
- 忘了闭区间长度是 r - l + 1。
- 只处理重叠，不处理相邻/包含关系导致漏并。
- 循环结束后漏算最后一个合并区间。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int countDays(int days, int[][] meetings) {
java.util.Arrays.sort(meetings, (a, b) -> {
if (a[0] != b[0]) return a[0] - b[0];
return a[1] - b[1];
});
long covered = 0;
int l = -1, r = -1;
for (int[] m : meetings) {
int s = m[0], e = m[1];
if (l == -1) {
l = s;
r = e;
} else if (s > r) {
covered += (long) (r - l + 1);
l = s;
r = e;
} else {
r = Math.max(r, e);
}
}
if (l != -1) covered += (long) (r - l + 1);
return (int) (days - covered);
}
}func countDays(days int, meetings [][]int) int {
sort.Slice(meetings, func(i, j int) bool {
if meetings[i][0] != meetings[j][0] {
return meetings[i][0] < meetings[j][0]
}
return meetings[i][1] < meetings[j][1]
})
covered := 0
l, r := -1, -1
for _, m := range meetings {
s, e := m[0], m[1]
if l == -1 {
l, r = s, e
} else if s > r {
covered += r - l + 1
l, r = s, e
} else if e > r {
r = e
}
}
if l != -1 {
covered += r - l + 1
}
return days - covered
}class Solution {
public:
int countDays(int days, vector<vector<int>>& meetings) {
sort(meetings.begin(), meetings.end());
long long covered = 0;
int l = -1, r = -1;
for (auto& m : meetings) {
int s = m[0], e = m[1];
if (l == -1) {
l = s;
r = e;
} else if (s > r) {
covered += (r - l + 1);
l = s;
r = e;
} else {
r = max(r, e);
}
}
if (l != -1) covered += (r - l + 1);
return (int)(days - covered);
}
};class Solution:
def countDays(self, days: int, meetings: List[List[int]]) -> int:
meetings.sort()
covered = 0
l = r = -1
for s, e in meetings:
if l == -1:
l, r = s, e
elif s > r:
covered += r - l + 1
l, r = s, e
else:
r = max(r, e)
if l != -1:
covered += r - l + 1
return days - covered/**
* @param {number} days
* @param {number[][]} meetings
* @return {number}
*/
var countDays = function(days, meetings) {
meetings.sort((a, b) => (a[0] - b[0]) || (a[1] - b[1]));
let covered = 0;
let l = -1, r = -1;
for (const [s, e] of meetings) {
if (l === -1) {
l = s;
r = e;
} else if (s > r) {
covered += (r - l + 1);
l = s;
r = e;
} else {
r = Math.max(r, e);
}
}
if (l !== -1) covered += (r - l + 1);
return days - covered;
};
Comments