LeetCode 757. 设置交集大小至少为2

Categories:

题目描述
思路分析
1. 解法一：贪心 + 排序（推荐）
相似题目

题目描述

✅ 757. 设置交集大小至少为2

思路分析

解法一：贪心 + 排序（推荐）

核心思路：

目标是找一个最小集合 S，使其与每个区间的交集大小至少为 2

按区间右端点升序排序，右端点相同时按左端点降序排序

维护集合中已选的最大两个元素 s1（最大）和 s2（次大）

对每个区间 [l, r]，判断当前 s1、s2 与该区间的覆盖情况：

若 s1 >= l 且 s2 >= l：已满足，跳过

若仅 s1 >= l：需再加一个点，贪心选 r-1（尽量靠右覆盖更多后续区间）

若 s1 < l：两者均不在区间内，需加两个点，选 r-1 和 r

复杂度分析：

时间复杂度：O(n log n)，其中 n 表示区间数量，排序主导

空间复杂度：O(log n)，排序所用递归栈空间

class Solution {
  public int intersectionSizeTwo(int[][] intervals) {
    // 按右端点升序，右端点相同时左端点降序
    Arrays.sort(intervals, (a, b) -> a[1] != b[1] ? a[1] - b[1] : b[0] - a[0]);

    int ans = 0;
    // s1: 集合中最大元素，s2: 次大元素
    int s1 = -1, s2 = -1;

    for (int[] interval : intervals) {
      int l = interval[0];
      int r = interval[1];

      if (s1 >= l && s2 >= l) {
        // 两个元素都已在区间内，满足条件
        continue;
      } else if (s1 >= l) {
        // 仅最大元素在区间内，再选一个靠右的点
        s2 = s1;
        s1 = r;
        ans++;
      } else {
        // 两个元素都不在区间内，选区间最右两个点
        s2 = r - 1;
        s1 = r;
        ans += 2;
      }
    }

    return ans;
  }
}

import "sort"

func intersectionSizeTwo(intervals [][]int) int {
    // 按右端点升序，右端点相同时左端点降序
    sort.Slice(intervals, func(i, j int) bool {
        if intervals[i][1] != intervals[j][1] {
            return intervals[i][1] < intervals[j][1]
        }
        return intervals[i][0] > intervals[j][0]
    })

    ans := 0
    // s1: 集合最大值，s2: 次大值
    s1, s2 := -1, -1

    for _, interval := range intervals {
        l, r := interval[0], interval[1]

        if s1 >= l && s2 >= l {
            // 两个元素均已覆盖，跳过
            continue
        } else if s1 >= l {
            // 仅最大值覆盖，新增一个点
            s2 = s1
            s1 = r
            ans++
        } else {
            // 均未覆盖，新增两个点
            s2 = r - 1
            s1 = r
            ans += 2
        }
    }

    return ans
}

相似题目

题目	难度	考察点
56. 合并区间	中等	排序 + 贪心
57. 插入区间	中等	区间合并
435. 无重叠区间	中等	贪心
452. 用最少数量的箭引爆气球	中等	贪心
986. 区间列表的交集	中等	双指针
759. 员工空闲时间	困难	区间合并

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/51516451