Java中如何遍历多组重叠区间实现全范围值无重复无遗漏遍历

核心规则说明 #

给定两个等长int数组start和end，start[i]、end[i]分别对应第i个闭区间的起点和终点，需要按数组索引从0到n-1的顺序遍历所有区间覆盖的整数，满足两个核心要求：

• 所有区间覆盖的整数全部遍历到，无遗漏
• 同一个整数不重复遍历，已经安排到后续区间遍历的数值，当前区间不重复处理

示例给定的输入如下：

int[] start = {1, 3, 4};
int[] end = {6, 10, 5};

最终覆盖的完整数值范围是1...10。

实现思路 #

核心逻辑非常直白：对于第i个区间里的任意整数，如果这个数会出现在i之后的任意一个区间里，就留给后续的区间去遍历，当前区间只处理那些后续不会再出现的数。
这个逻辑天然满足无重复、无遗漏的要求：每个整数一定会属于至少一个区间，我们只需要在包含它的索引最大的那个区间里遍历它即可，既不会提前在前面的区间重复处理，也不会因为所有区间都跳过而遗漏。
如果需要完全匹配示例里的端点归属（比如公共端点3归第0个区间遍历），只需要微调端点的判断条件即可，不影响核心逻辑。

代码实现 #

易懂版（适合小数据量场景） #

逻辑直白不易错，不需要复杂预处理，直接按规则模拟即可：

public class IntervalTraversal {
    public static void main(String[] args) {
        int[] start = {1, 3, 4};
        int[] end = {6, 10, 5};
        int n = start.length;

        // 按索引顺序处理每个区间
        for (int i = 0; i < n; i++) {
            int curS = start[i];
            int curE = end[i];
            System.out.printf("区间%d[%d,%d] 遍历数值：", i, curS, curE);

            for (int num = curS; num <= curE; num++) {
                boolean hasInLater = false;
                // 检查当前数是否在后续任意区间中存在
                for (int j = i + 1; j < n; j++) {
                    if (num >= start[j] && num <= end[j]) {
                        hasInLater = true;
                        break;
                    }
                }
                // 后续不存在则当前遍历
                if (!hasInLater) {
                    System.out.print(num + " ");
                }
            }
            System.out.println();
        }
    }
}

运行输出：

区间0[1,6] 遍历数值：1 2 
区间1[3,10] 遍历数值：3 6 7 8 9 10 
区间2[4,5] 遍历数值：4 5 

可以看到所有1-10的数全部被遍历，无重复无遗漏。如果要完全匹配示例里把3归到第0个区间的效果，只需要把后续区间的判断条件从num >= start[j]改成num > start[j]，再增加一个已遍历集合做去重即可，本质只是闭区间端点的归属规则差异。

优化版（适合大数据量场景） #

如果区间范围很大（比如覆盖到百万级数值），上面的逐数判断效率较低，可以先从后往前预处理，维护后续区间的合并集合，把时间复杂度降到O(nlogn)：

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class IntervalTraversalOpt {
    // 区间结构
    static class Range {
        int s;
        int e;
        public Range(int s, int e) {
            this.s = s;
            this.e = e;
        }
    }

    public static void main(String[] args) {
        int[] start = {1, 3, 4};
        int[] end = {6, 10, 5};
        int n = start.length;
        List<Range> laterRanges = new ArrayList<>();

        for (int i = n-1; i >=0 ; i--) {
            int curS = start[i];
            int curE = end[i];
            System.out.printf("区间%d[%d,%d] 遍历数值：", i, curS, curE);

            // 求当前区间和后续所有区间的差集，就是当前需要遍历的段
            List<Range> needTraverse = new ArrayList<>();
            needTraverse.add(new Range(curS, curE));
            for (Range r : laterRanges) {
                List<Range> temp = new ArrayList<>();
                for (Range cur : needTraverse) {
                    // 没有交集直接保留
                    if (cur.e < r.s || cur.s > r.e) {
                        temp.add(cur);
                        continue;
                    }
                    // 有交集，切掉重叠部分
                    if (cur.s < r.s) {
                        temp.add(new Range(cur.s, r.s -1));
                    }
                    if (cur.e > r.e) {
                        temp.add(new Range(r.e +1, cur.e));
                    }
                }
                needTraverse = temp;
            }

            // 输出当前需要遍历的段
            for (Range r : needTraverse) {
                for (int num = r.s; num <= r.e; num++) {
                    System.out.print(num + " ");
                }
            }
            System.out.println();

            // 把当前区间合并到后续区间集合中，供前一个i使用
            laterRanges.add(new Range(curS, curE));
            // 合并重叠区间，减少后续计算量
            laterRanges.sort(Comparator.comparingInt(a -> a.s));
            List<Range> merged = new ArrayList<>();
            for (Range r : laterRanges) {
                if (merged.isEmpty()) {
                    merged.add(r);
                    continue;
                }
                Range last = merged.get(merged.size()-1);
                if (r.s <= last.e +1) {
                    last.e = Math.max(last.e, r.e);
                } else {
                    merged.add(r);
                }
            }
            laterRanges = merged;
        }
    }
}

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