面试算法74:合并区间

发布时间:2023年12月28日

题目

输入一个区间的集合,请将重叠的区间合并。每个区间用两个数字比较,分别表示区间的起始位置和结束位置。例如,输入区间[[1,3],[4,5],[8,10],[2,6],[9,12],[15,18]],合并重叠的区间之后得到[[1,6],[8,12],[15,18]]。

分析

例如,如果将区间列表[[1,3],[4,5],[8,10],[2,6],[9,12],[15,18]]按照起始位置排序就可以得到[[1,3],[2,6],[4,5],[8,10],[9,12],[15,18]]。接下来扫描排序之后的区间。区间[1,3]和[2,6]重叠,可以合并,它们合并之后得到区间[1,6]。接下来的区间[1,6]和[4,5]重叠,也可以合并,它们合并之后得到区间[1,6]。由于区间[1,6]与下一个区间[8,10]不重叠,因此将区间[1,6]保存到合并之后的区间列表中,然后从区间[8,10]开始与后面的区间合并。区间[8,10]与它的下一个区间[9,12]重叠,合并之后得到区间[8,12]。由于区间[8,12]与下一个区间[15,18]不重叠,因此将区间[8,12]添加到合并之后的区间列表中,再从下一个区间[15,18]开始合并之后的区间。最终合并之后的区间列表是[[1,6],[8,12],[15,18]]。

public class Test {
    public static void main(String[] args) {
        int[][] intervals = {{1, 3}, {4, 5}, {8, 10}, {2, 6}, {9, 12}, {15, 18}};
        int[][] merge = merge(intervals);
        for (int[] item : merge) {
            System.out.println(item[0] + "," + item[1]);
        }
    }

    public static int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (i1, i2) -> i1[0] - i2[0]);

        List<int[]> merged = new LinkedList<>();
        int i = 0;
        while (i < intervals.length) {
            int[] temp = {intervals[i][0], intervals[i][1]};
            int j = i + 1;
            while (j < intervals.length && intervals[j][0] <= temp[1]) {
                temp[1] = Math.max(temp[1], intervals[j][1]);
                j++;
            }

            merged.add(temp);
            i = j;
        }

        int[][] result = new int[merged.size()][];
        return merged.toArray(result);
    }
}
文章来源:https://blog.csdn.net/GoGleTech/article/details/135265636
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。