7. Maximum Number of Non-Overlapping Intervals

Given an array of intervals where each interval has a start and end time, return the maximum number of non-overlapping intervals.

Examples

Example 1

Input:

meetings = [[1, 2], [2, 3], [3, 4], [1, 3]]

Output:

3

Explanation:

Step 1: Sort meetings by end time → [[1,2],[2,3],[1,3],[3,4]].
 
Step 2: Select [1,2] (count=1, last_end=2).
 
Step 3: [2,3] has start 2 ≥ 2, select (count=2, last_end=3).
 
Step 4: [1,3] start 1 < 3, skip.
 
Step 5: [3,4] start 3 ≥ 3, select (count=3). Result = 3.

Example 2

Input:

meetings = [[0, 5], [0, 1], [1, 2], [2, 3], [3, 5], [4, 6]]

Output:

4

Explanation:

Step 1: Sort by end time → [[0,1],[1,2],[2,3],[3,5],[0,5],[4,6]].
 
Step 2: Select [0,1] (count=1, end=1).
 
Step 3: [1,2] (count=2, end=2).
 
Step 4: [2,3] (count=3, end=3).
 
Step 5: [3,5] (count=4, end=5). Skip [0,5] and [4,6] because their start times are before last_end=5. Result = 4.

Input Format

The first line contains a single integer, meetings_rows, representing the total number of meetings.

The second line contains a single integer, meetings_columns, representing the number of properties for each meeting (typically 2 for a start and end time).

The next meetings_rows lines describe the meetings. Each line contains meetings_columns space-separated integers, representing the properties of a single meeting.

6
2
1 2
3 4
0 6
5 7
8 9
5 9

Explanation:

The first line, 6, is the value for meetings_rows.
 
The second line, 2, is the value for meetings_columns.
 
The following 6 lines represent the individual meetings, which are parsed into a 2D list: [[1, 2], [3, 4], [0, 6], [5, 7], [8, 9], [5, 9]].
 
Constraints
 
0 <= meetings.length <= 1000
 
meetings[i].length == 2 for all 0 <= i < meetings.length
 
0 <= meetings[i][0] < meetings[i][1] <= 10^9
 
All start and end times are integers
 
Meetings may share start or end times

Output Format

Return a single integer denoting the maximum number of non-overlapping meetings that can be scheduled.

Sample Input 0

1
2
5 10

Sample Output 0

1

Sample Input 1

3
2
1 2
2 3
3 4

Sample Output 1

3

Resolution

核心思路： 贪心算法——按结束时间排序，每次选择最早结束且不与已选区间重叠的区间。

为什么按结束时间排序是对的？ 结束越早的区间，给后面留下的空间越大，越有机会安排更多区间。这是一个经典的贪心选择性质：局部最优能导出全局最优。

算法步骤：

1. 按结束时间升序排序
2. 选第一个区间（最早结束的）
3. 遍历剩余区间，只要 start >= lastEnd 就选，并更新 lastEnd

复杂度：

• 时间复杂度：O(n log n)，排序占主导
• 空间复杂度：O(1)，原地排序无额外空间

同类题： 这道题等价于 LeetCode 435. 无重叠区间（求最多不重叠区间 = 总区间数 - 最少删除区间数）。

我的解法

function maximizeNonOverlappingMeetings(meetings: number[][]): number {
    // Write your code here
    if (!meetings.length) return 0
    meetings.sort((a, b) => a[1] - b[1])
    let count = 1
    let lastEnd = meetings[0][1]
    for (let i = 1; i < meetings.length; i++) {
        if (meetings[i][0] >= lastEnd) {
            count++
            lastEnd = meetings[i][1] 
        } 
    }
    return count
}

思路： 按结束时间排序后，贪心地选择第一个区间，然后遍历后续区间，不重叠就选。

复杂度：

• 时间复杂度：O(n log n)，排序占主导，遍历 O(n)
• 空间复杂度：O(1)

优化说明： 循环从 i = 1 开始（第一个区间已默认选中，不需要再和自己比较）。

核心思考：贪心策略的本质

1. 为什么按结束时间排序是对的？

贪心的核心在于**“资源尽早释放”**。 想象时间轴是一条直线，我们要往里塞尽可能多的木块。

• 选结束最早的区间，意味着剩下的可用时间最长（留给后续的选择空间最大）。
• 这不仅仅是直觉，在数学上可以通过**“替换法” (Exchange Argument)** 严格证明：假设存在一个最优解不包含结束最早的区间 A，我们可以把最优解里的第一个区间替换为 A。因为 A 结束得比任何其他区间都早，这种替换绝不会导致后续冲突增加，只会让剩余时间变多。因此，贪心选择永远是安全的。

2. 为什么不按开始时间排序？

开始早不代表“占用少”。 反例： [[1, 100], [2, 3], [4, 5]]

• 按开始时间排：先选 [1, 100]，结果后面的 [2, 3] 和 [4, 5] 全部因为重叠被跳过。最终只选了 1 个。
• 按结束时间排：先选 [2, 3]，再选 [4, 5]，跳过 [1, 100]。最终选了 2 个（最优）。 结论：开始早的区间可能是个“时间黑洞”，直接吃掉了后面所有短区间的生存空间。

3. 举一反三：贪心何时失效？

贪心算法极其高效（O(n log n)），但它只对**“局部最优能推导全局最优”**的问题有效。 如果题目条件稍作修改，贪心就会失效：

• 加权区间调度问题 (Weighted Interval Scheduling)：如果每个会议有不同的重要性/价值（比如有的会赚 10 块，有的赚 1000 块），单纯追求“数量最多”或“结束最早”就不够了。此时必须使用动态规划 (DP) 来计算总价值最大化。
• 区间覆盖问题：如果目标是“用最少的区间覆盖整个时间段”，贪心策略会变为“每次选能覆盖当前起点且结束最远的区间”。