20260628-统计不重叠区间的个数（N0040）- 算法机考高频题型 · 华为OD / 贪心题解 | AlgoMooc

N0040. 20260628-统计不重叠区间的个数

中等

通过率 55% · 提交 11 · 通过 6

100分华为OD贪心区间

本题改编自算法机考高频题型 · 考点：100分 / 华为OD · 难度：中等

给定一个以二维数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [start_ end_i]（start_i 和 end_i 都是整数），这些区间之间可能存在重叠，请统计跟其他任何区间都不重叠的区间数量。

这类题属于算法机考高频题型中「100分 / 华为OD」方向的高频题型，通常考察对「100分 / 华为OD」的建模能力与边界条件处理。掌握本题的解题思路后，可举一反三应对同类真题方向，稳步提升机考通过率。

补充说明

补充说明：

1 ≤ intervals.length ≤ 10000
intervals[i].length == 2
0 ≤ starti_ ≤ end_i ≤ 10000

输入描述

一个二维数组 intervals，每一行输入对应 intervals[i]。 intervals[i] 表示第 i 个区间，intervals[i][0] 表示第 i 个区间的 start_i，intervals[i][1] 表示第 i 个区间的 end_i。

输出描述

这个区间集合中跟其他区间都不重叠的区间数量。

示例

示例 1

输入示例

输出示例

说明：

区间 [8,10] 和 [15,18] 跟其他区间都不重合

示例 2

输入示例

2
2 4
4 6

输出示例

说明：

[2,4] 和 [4,6] 这 2 个区间重叠，不存在跟其他区间都不重叠的区间，故返回 0

时间限制 1000 ms · 内存限制 256 MB

本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。

问小欧 · 图解算法年卡¥99 开通 →

字号13Ctrl+/ 注释 · Ctrl+↵ 提交

from typing import List

# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
# @param intervals 一个二维数组，表示若干个区间的集合
# @return 跟其他任何区间都不重叠的区间数量
class Solution:
    def findNonOverlappingIntervals(self, intervals: List[List[int]]) -> int:
        pass

# 以下内容为LeetCode核心代码模式转为ACM模式所需代码
# 请在algomooc oj上直接使用，在实际考试中无需编写

def main():
    n = int(input().strip())
    intervals = []
    for _ in range(n):
        line = input().strip()
        while line == "":
            line = input().strip()
        start, end = map(int, line.split())
        intervals.append([start, end])
    
    sol = Solution()
    print(sol.findNonOverlappingIntervals(intervals))

if __name__ == "__main__":
    main()

写完代码点「提交」，将对全部测试用例判题。