设置交集大小至少为2

难度:

标签:

题目描述

You are given a 2D integer array intervals where intervals[i] = [start_i, end_i] represents all the integers from start_i to end_i inclusively.

A containing set is an array nums where each interval from intervals has at least two integers in nums.

For example, if intervals = [[1,3], [3,7], [8,9]], then [1,2,4,7,8,9] and [2,3,4,8,9] are containing sets.

Return the minimum possible size of a containing set.

Example 1:

Input: intervals = [[1,3],[3,7],[8,9]]
Output: 5
Explanation: let nums = [2, 3, 4, 8, 9].
It can be shown that there cannot be any containing array of size 4.

Example 2:

Input: intervals = [[1,3],[1,4],[2,5],[3,5]]
Output: 3
Explanation: let nums = [2, 3, 4].
It can be shown that there cannot be any containing array of size 2.

Example 3:

Input: intervals = [[1,2],[2,3],[2,4],[4,5]]
Output: 5
Explanation: let nums = [1, 2, 3, 4, 5].
It can be shown that there cannot be any containing array of size 4.

Constraints:

1 <= intervals.length <= 3000
intervals[i].length == 2
0 <= start_i < end_i <= 10⁸

代码结果

运行时间: 33 ms, 内存: 17.2 MB

/*
 * 使用Java Stream的解法:
 * 我们同样需要最小包含集合。我们先对区间按右端点升序排序，然后遍历每个区间，
 * 选择两个新的数字或者复用已有的数字。
 */
import java.util.Arrays;
import java.util.Comparator;
import java.util.stream.IntStream;

public class Solution {
    public int intersectionSizeTwo(int[][] intervals) {
        // 按右端点排序
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[1]));
        int[] result = {0};
        int[] largest = {-1, -1};

        IntStream.range(0, intervals.length).forEach(i -> {
            int start = intervals[i][0];
            int end = intervals[i][1];

            if (largest[1] < start) {
                largest[0] = end - 1;
                largest[1] = end;
                result[0] += 2;
            } else if (largest[0] < start) {
                largest[0] = largest[1];
                largest[1] = end;
                result[0] += 1;
            }
        });

        return result[0];
    }
}

解释

方法:

本题采用贪心算法，按区间结束位置排序，当结束位置相同时按起始位置降序排序。遍历区间，根据当前选择的点和区间的起始位置，分为三种情况：1.当前区间与已选点无交集，需要添加该区间的最后两个点；2.当前区间与已选点有一个交集，只需添加该区间的最后一个点；3.当前区间与已选点有至少两个交集，不需要添加任何点。最终返回选择的点的总数。

时间复杂度:

O(nlogn)

空间复杂度:

O(n)

代码细节讲解

🦆

为什么在对区间进行排序时，要首先根据结束位置升序排序，紧接着对起始位置进行降序排序？这样的排序策略有什么特别的优势吗？

▷

这种排序策略主要是为了简化后续的贪心选择过程。首先，根据区间的结束位置升序排序，确保在处理当前区间时，之前的区间都已被处理，可以有效地使用已选择的点来尽可能覆盖多个区间。其次，当多个区间有相同的结束位置时，按照起始位置降序排序使得起始位置较晚的区间先被处理，这样可以更容易地使用已经选择的点来覆盖这些区间，减少额外点的添加。这种排序方法有助于我们从左到右处理区间，并尽可能利用已选择的点，避免不必要的重叠和点的浪费。

🦆

在贪心算法的执行过程中，你是如何确保每个区间至少有两个整数在`nums`中的？具体的判断逻辑是什么？

▷

在算法执行过程中，通过对每个遍历到的区间，基于已选择点的情况（存在于列表`points`中），进行判断和处理。具体逻辑如下：1. 如果区间的起始点大于`points`中最后一个点，说明当前区间与已选点无交集，此时需添加该区间的最后两个点，即`interval[1]-1`和`interval[1]`，确保此区间被至少两个点覆盖。2. 如果区间的起始点大于`points`中倒数第二个点但小于或等于最后一个点，说明当前区间与已选点正好有一个交集，此时只需添加`interval[1]`，以确保区间被两个点覆盖。这样的处理确保了每个区间至少被两个点覆盖。

🦆

如果一个区间的开始点恰好等于`points`中最后一个点，这种情况下的处理策略是什么？题解中似乎没有明确说明。

▷

如果区间的开始点恰好等于`points`中最后一个点，这意味着当前区间与已选的点集有恰好一个交集点（即`points`中最后一个点）。在这种情况下，根据贪心算法的逻辑，我们仅需要再添加一个点，即区间的结束点`interval[1]`，以满足题目要求的至少有两个点覆盖每个区间的条件。这样不仅确保了覆盖，还保持了选择点数的最小化。

设置交集大小至少为2

题目描述

代码结果

解释

代码细节讲解

相关问题