区间合并优化：滑动窗口指针管理问题咨询

问题描述 #

给定一组闭区间（每个区间由起始值a[i]和结束值b[i]定义），以及可插入的单个区间的最大长度k。目标是插入一个长度≤k的区间，使合并后的不连通区间总数最少。

示例 #

示例1 #

输入：

Intervals = [(1, 5), (2, 4), (6, 6), (7, 14), (16, 19)]
k = 2

• 最优解：插入区间(5,7)（长度等于k），合并后得到2个不连通组；
• 次优解：插入(14,16)则得到3个组。

示例2 #

输入：

Intervals = [(1,3),(4,6),(7,9),(10,11),(13,15)]
k = 10

• 最优解：插入(3,13)可将所有区间合并为1个组。

约束条件 #

1 <= n <= 2 * 10^5
1 <= a[i] <= b[i] <= 10^9
1 <= k <= 10^9

我的代码 #

import java.util.*;

public class Main {
    public static void main(String[] args) {
        List<Integer> a1 = Arrays.asList(1, 2, 5, 10);
        List<Integer> b1 = Arrays.asList(2, 4, 8, 11);
        int k1 = 2;
        System.out.println(solve(a1, b1, k1));  // Output: 2

        List<Integer> a2 = Arrays.asList(3, 2, 3);
        List<Integer> b2 = Arrays.asList(5, 9, 3);
        int k2 = 10;
        System.out.println(solve(a2, b2, k2));  // Output: 1

        List<Integer> a3 = Arrays.asList(1, 2, 6, 7, 16);
        List<Integer> b3 = Arrays.asList(5, 4, 6, 14, 19);
        int k3 = 2;
        System.out.println(solve(a3, b3, k3));  // Output: 2 

        List<Integer> a4 = Arrays.asList(2,13,27,45,45,33);
        List<Integer> b4 = Arrays.asList(10,24,40,45,45,33);
        int k4 = 12;
        System.out.println(solve(a4, b4, k4));  // Output: 3 
    }
    public static int solve(List<Integer> a, List<Integer> b, int k) {
        int n = a.size();
        int[][] intervals = new int[n][2];
        for (int i = 0; i < n; i++) {
            intervals[i][0] = a.get(i);
            intervals[i][1] = b.get(i);
        }

        // Sort by start time
        Arrays.sort(intervals, Comparator.comparingInt(x -> x[0]));

        // Merge intervals in-place
        List<int[]> merged = new ArrayList<>();
        int[] curr = intervals[0];
        for (int i = 1; i < n; i++) {
            if (curr[1] >= intervals[i][0]) {
                curr[1] = Math.max(curr[1], intervals[i][1]);
            } else {
                merged.add(curr);
                curr = intervals[i];
            }
        }
        merged.add(curr);

        int m = merged.size();
        if (m == 1) return 1;

        // Sliding window to bridge max gaps
        int maxBridged = 0;
        int left = 0;
        for (int right = 0; right < m - 1; right++) {
            int start = merged.get(left)[1];
            int end = merged.get(right + 1)[0];
            while (end - start > k) {
                left++;
                start = merged.get(left)[1];
            }
            maxBridged = Math.max(maxBridged, right - left + 1);
        }

        return m - maxBridged;
    }
}

遇到的问题 #

我尝试用滑动窗口法找出合并后区间间可被单个长度≤k的区间桥接的最大间隙数，但在左右指针的管理上遇到困难：

• 右指针应如何在循环中推进？
• 如何确保左指针不会越界或错误地超过右指针？

内容的提问来源于stack exchange，提问作者CodeCrusader