757. Set Intersection Size At Least Two
2024-10-19 04:35:01
An integer interval [a, b]
(for integers a < b
) is a set of all consecutive integers from a
to b
, including a
and b
.
Find the minimum size of a set S such that for every integer interval A in intervals
, the intersection of S with A has size at least 2.
Example 1:
Input: intervals = [[1, 3], [1, 4], [2, 5], [3, 5]]
Output: 3
Explanation:
Consider the set S = {2, 3, 4}. For each interval, there are at least 2 elements from S in the interval.
Also, there isn't a smaller size set that fulfills the above condition.
Thus, we output the size of this set, which is 3.
Example 2:
Input: intervals = [[1, 2], [2, 3], [2, 4], [4, 5]]
Output: 5
Explanation:
An example of a minimum sized set is {1, 2, 3, 4, 5}.
Note:
intervals
will have length in range[1, 3000]
.intervals[i]
will have length2
, representing some integer interval.intervals[i][j]
will be an integer in[0, 10^8]
.
Approach #1: C++. [greedy]
class Solution {
public:
int intersectionSizeTwo(vector<vector<int>>& intervals) {
int size = intervals.size();
sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {
if (a[1] == b[1]) return a[0] > b[0];
else return a[1] < b[1];
}); int ans = 0, p1 = -1, p2 = -1;
for (int i = 0; i < size; ++i) {
if (intervals[i][0] <= p1) continue;
if (intervals[i][0] > p2) {
ans += 2;
p2 = intervals[i][1];
p1 = p2 - 1;
} else {
ans++;
p1 = p2;
p2 = intervals[i][1];
}
} return ans;
}
};
最新文章
- Entity Framework 6 Recipes 2nd Edition(9-5)译->;删除一个断开的实体
- MyBatis学习总结(二)——使用MyBatis对表执行CRUD操作(转载)
- [DPDK][转]DPDK编程开发(4)—lcore
- 【Visual Lisp】块专题
- ios-chart 不支持渐变的底色 --- 后面支持了渐变
- maven本地仓库
- NDK中, 如何提高脚本式语言的可读性
- clients(PV操作共享内核内存进行输入输出分屏) - server(进程间通信)模型实现
- ☀【offset() / position()】
- 支持“***Context”上下文的模型已在数据库创建后发生更改。请考虑使用 Code First 迁移更新数据库(http://go.microsoft.com/fwlink/?LinkId=238269)。
- SQL Server高可用——日志传送(4-2)——部署
- php短数组写法
- Java加密与解密笔记(三) 非对称加密
- 分享html5的一个拖拽手法
- 在Qt中配置TBB以及简单实用
- linux抓包工具Charles的配置安装
- abp Cannot access a disposed object. A common cause of this error is disposing
- Netsharp总体设计
- VirtualBox 报错VERR_VD_IMAGE_READ_ONLY
- linux下gzip的压缩详解