757. Set Intersection Size At Least Two
set at size two Least intersection
2023-09-11 14:22:45 时间
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; } };
相关文章
- Can HTML checkboxes be set to readonly?
- 百度LBS云搜索时报错 "filter:area is not filteable field, please set property in the cloud-storage
- Java 集合List、Set、HashMap操作一(Array转List、Set排序、HashMap遍历、Set遍历、List遍历、HashMap大小长度、List打乱顺序)
- python公共操作(运算符(+、*、in、not in)、公共方法(len()、del、max()、min()、range()、enumerate())、类型转换(tuple、list、set))
- 15Redis - 存储set(使用场景)
- set的相关习题
- oracle中SET DEFINE意思
- Redis第十一讲 Redis之Set底层数据结构实现
- mybatis和mybatiplus中Error attempting to get column ‘xx‘ from result set
- set常见操作:
- tensoflow模型中提示:ValueError: Variable rnn/basic_rnn_cell/kernel already exists, disallowed. Did you mean to set reuse=True or reuse=tf.AUTO_REUSE in VarScope? 解决办法
- Vue.set 向响应式对象中添加响应式属性,及设置数组元素触发视图更新
- Java中List Set Map 总结
- stl之set
- mysqlbinlog报错,unknown variable 'default-character-set=utf8'
- RabbitMQ>Erlang machine stopped instantly (distribution name conflict?). The service is not restarted as OnFail is set to ignore.-报错解决方案 原来是NNND。。。
- [LeetCode] 902. Numbers At Most N Given Digit Set 最大为 N 的数字组合
- mysql 模糊查询语句比较(LIKE、instr、locate、find_in_set、position)
- 902. Numbers At Most N Given Digit Set
- Semi-Prime(set)