2022-10-11:一个整数区间 [a, b] ( a < b ) 代表着从 a 到 b 的所有连续整数,包括 a 和 b。 给你一组整数区间interval
一个 2022 10 所有 11 整数 包括 连续
2023-06-13 09:13:52 时间
2022-10-11:一个整数区间 a, b 代表着从 a 到 b 的所有连续整数,包括 a 和 b。
给你一组整数区间intervals,请找到一个最小的集合 S,
使得 S 里的元素与区间intervals中的每一个整数区间都至少有2个元素相交。
输出这个最小集合S的大小。
输入: intervals = [1, 2, 2, 3, 2, 4, 4, 5]。
输出: 5。
答案2022-10-11:
力扣757。
贪心。先按结尾数字升序排序,再按开始数字降序排序。
第一个整数区间,先选靠后的两个数字。
java,go,rust运行情况见截图。java和go运行最快,go运行速度落后了。内存占用上,rust占用内存最少,go次之,java最高。
代码用rust编写。代码如下:
impl Solution {
pub fn intersection_size_two(intervals: Vec<Vec<i32>>) -> i32 {
let mut intervals = intervals;
// O(N*logN)
// 区间根据,结束位置谁小,谁在前
// 结束位置一样的,开头位置谁大,谁在前
intervals.sort_by(|a, b| {
if a[1] != b[1] {
a[1].cmp(&b[1])
} else {
b[0].cmp(&a[0])
}
});
// 区间排好序了
// [1,7] [2,8] [1,8] [13,40]
let n = intervals.len() as i32;
// [1,7] pre = 6 pos =7
let mut pos = intervals[0][1];
let mut pre = pos - 1;
let mut ans = 2;
for i in 1..n {
// intervals[i] = {开头,结尾}
// 6 7 [<=6, 结尾]
//
// if(intervals[i][0] <= pre) {
// continue;
// }
// >6 讨论!
if intervals[i as usize][0] > pre {
// 6 7 [开头>6, 结尾]
// 1) 6 < 开头 <= 7
// 只有7满足了当前的区间,我们要加个数字,结尾
// 6 7 结尾
// pre pos
// 6 7
// 2) 6 < 开头、7 < 开头
// 结尾-1 结尾
// pre pos
if intervals[i as usize][0] > pos {
// 对应的就是情况2)
pre = intervals[i as usize][1] - 1;
ans += 2;
} else {
// 对应的就是情况1)
pre = pos;
ans += 1;
}
// 不管情况2)还是情况1)都需要这一句
pos = intervals[i as usize][1];
}
}
return ans;
}
}
fn main() {
let rectangles = vec![vec![1, 2], vec![2, 3], vec![2, 4], vec![4, 5]];
let ans = Solution::intersection_size_two(rectangles);
println!("ans = {:?}", ans);
}
struct Solution {}
执行结果如下:
相关文章
- 遗传算法的应用实例python实现_遗传算法Python解决一个问题
- 2022-10-01:给定一个字符串 s,计算 s 的 不同非空子序列 的个数 因为结果可能很大,所以返回答案需要对 10^9 + 7 取余 。 字符串的 子序
- 2022-10-03:给定一个正数n,比如6 表示数轴上有 0,1,2,3,4,5,6 <0 或者 >6 的位置认为无法到达 给定两个数字x和y,0<= x,y
- 2022-10-05:在一个 n x n 的整数矩阵 grid 中, 每一个方格的值 grid[i][j] 表示位置 (i, j) 的平台高度。 当开始下雨时,
- 2022-10-07:给定员工的 schedule 列表,表示每个员工的工作时间。 每个员工都有一个非重叠的时间段 Intervals 列表,这些时间段已经排好
- 2022-10-17:特殊的二进制序列是具有以下两个性质的二进制序列: 0 的数量与 1 的数量相等。 二进制序列的每一个前缀码中 1 的数量要大于等于 0 的
- 2022-10-19:一个数组如果满足 : 升降升降升降... 或者 降升降升...都是满足的 给定一个数组, 1,看有几种方法能够剔除一个元素,达成上述的要求
- 2022-10-25:在一个 2 * 3 的板上(board)有 5 块砖瓦,用数字 1~5 来表示, 以及一块空缺用 0 来表示。一次 移动 定义为选择 0
- 2022-10-27:设计一个数据结构,有效地找到给定子数组的 多数元素 。 子数组的 多数元素 是在子数组中出现 threshold 次数或次数以上的元素。
- 2022-08-10:为了给刷题的同学一些奖励,力扣团队引入了一个弹簧游戏机,游戏机由 N 个特殊弹簧排成一排,编号为 0 到
- 2022-09-11:arr是一个可能包含重复元素的整数数组,我们将这个数组分割成几个“块”,并将这些块分别进行排序。之后再连接
- 2022-09-27:给定一个棵树,树上每个节点都有自己的值,记录在数组nums里,比如nums[4] = 10,表示4号点的值
- 2022-10-11:一个整数区间 [a, b] ( a < b ) 代表着从 a 到 b 的所有连续整数,包括 a 和 b。
- 2022-10-15:给你一个整数数组 nums 和一个整数 k ,请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返
- 2022-11-07:给你一个 n 个节点的 有向图 ,节点编号为 0 到 n - 1 ,其中每个节点 至多 有一条出边。 图用一个大小为 n 下标从 0 开始
- 2022-11-11:设计一个最大栈数据结构,既支持栈操作,又支持查找栈中最大元素。 实现 MaxStack 类: MaxStack() 初始化栈对象 void
- 2022-12-10:给你一个由小写字母组成的字符串 s ,和一个整数 k 如果满足下述条件,则可以将字符串 t 视作是 理想字符串 : t 是字符串 s 的一
- ECCV 2022 | 谷歌提出Data-free NAS,网络搜索仅需一个预训练模型
- 一个奇淫巧技的爬虫方法2022.8.16
- 2022-11-04:给定一个正数n,表示有多少个节点给定一个二维数组edges,表示所有无向边edges[i] = {a, b
- 【Rust日报】2022-12-17 Forma,一个高效的矢量图形渲染器
- Hibernate Criteria接口 createCriteria方法:创建一个新的Criteria对象