757. Set Intersection Size At Least Two
757. Set Intersection Size At Least Two
题目: https://leetcode.com/problems/set-intersection-size-at-least-two/
难度: Hard
题意：
- 给定n个区间
- 求一个最小集合，使得每个区间，集合中至少有两个数在区间里面
思路：
- 这题是贪心题
- 先对区间右端点排序。再从右端点小的开始贪心。每次先判断当前集合中是否有两个数在这个区间中，如果有，直接跳过，没有，从右端点开始往集合丢数，直到有两个数在这个区间中
- 直观的解释就是，为了满足前面的区间的条件，而丢进集合的数一定是越大越好，这样跟后面的区间共用一个数的几率会更大
解法：
class Solution {
public int intersectionSizeTwo(int[][] intervals) {
Integer[] array = new Integer[intervals.length];
for (int i = 0;i < array.length;i++) {
array[i] = i;
}
Arrays.sort(array, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return Integer.compare(intervals[o1][1], intervals[o2][1]);
}
});
List<Integer> result = new ArrayList<Integer>();
int[] t = new int[2];
for (int i = 0;i < array.length;i++) {
int n = 0;
if (result.size() > 0 && result.get(result.size() - 1) >= intervals[array[i]][0]) {
t[n++] = result.get(result.size() - 1);
}
if (result.size() > 1 && result.get(result.size() - 2) >= intervals[array[i]][0]) {
t[n++] = result.get(result.size() - 2);
}
int res = n;
int j = intervals[array[i]][1];
while (n != 2) {
boolean found = false;
for (int k = 0;k < n;k++) {
if (t[k] == j) {
found = true;
break;
}
}
if (found) {
j--;
} else {
t[n++] = j--;
}
}
if (res == 0) {
result.add(t[1]);
result.add(t[0]);
}
if (res == 1) {
result.add(t[1]);
}
}
return result.size();
}
}
