Leetcode每日一题：设置交集大小至少为2的贪心算法解法

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 (int interval : intervals) {
            if (interval[0] > y) {
                ans += 2;
                x = interval[1] - 1;
                y = interval[1];
            } else if (interval[0] > x) {
                ans++;
                x = y;
                y = interval[1];
            }
        }
        return ans;
    }

1 post - 1 participant

via - (author: 魔法师)