Skip to content

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

题意:

  1. 给定n个区间
  2. 求一个最小集合,使得每个区间,集合中至少有两个数在区间里面

思路:

  • 这题是贪心题
  • 先对区间右端点排序。再从右端点小的开始贪心。每次先判断当前集合中是否有两个数在这个区间中,如果有,直接跳过,没有,从右端点开始往集合丢数,直到有两个数在这个区间中
  • 直观的解释就是,为了满足前面的区间的条件,而丢进集合的数一定是越大越好,这样跟后面的区间共用一个数的几率会更大

解法:

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();
    }
}


回到顶部