魔法师 (@Constanline) 在 Leetcode每日一题 —— 757. 设置交集大小至少为2 中发帖
757. 设置交集大小至少为2
思路
第一反应是贪心或者线段树。仔细想想线段树并不合适,贪心好像可以,但是怎么贪是个问题。按题意肯定要贪覆盖范围最广的那个,如果我们按照区间最大点升序最小点降序排序,那么区间最后的值一定是范围最广的那个。我们留最后两个取值x、y,遍历区间,根据当前区间包含x、y的情况更新x、y并计数。
代码
public int intersectionSizeTwo(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> a[1] == b[1] ? b[0] - a[0] : a[1] - b[1]);
int ans = 0;
int x = Integer.MIN_VALUE, y = Integer.MIN_VALUE;
for (i...