0757. Set Intersection Size At Least Two

题目信息

题号:

0757

难度:

Hard

主题:

区间、集合、最小规模

原题:

LeetCode 0757

重点:

每个闭区间表示其中全部整数;需要选择一个整数集合,使每个区间内至少包含两个被选整数,并只返回集合的最小可能大小

题目重述

给定若干闭区间 intervals,其中 intervals[i] = [start_i, end_i] 表示从 start_i 到 end_i 的全部整数,并且 start_i < end_i。

需要选择一个由不同整数组成的集合 nums,使每个给定区间都至少包含 nums 中的两个整数。请返回满足条件的集合所能达到的最小元素个数;不需要返回集合本身。

1 <= intervals.length <= 3000,每个区间都含两个端点,并满足 0 <= start_i < end_i <= 10^8。

自建示例

两端区间互不相交:

输入:intervals = [[0,2],[1,4],[4,6]]
输出:4
解释:可以选择集合 {1,2,4,5}。第一个区间含 1、2,第二个区间含 1、2、4,第三个区间含 4、5。由于区间 [0,2] 与 [4,6] 各自都至少需要两个元素且彼此不相交,少于 4 个元素不可能满足要求。

多个区间共享同一对整数:

输入:intervals = [[2,5],[3,6],[4,7]]
输出:2
解释:集合 {4,5} 中的两个整数同时位于三个区间内,因此已经满足所有区间;任何合法集合至少需要两个元素。