首页 > 试题广场 >

区间列表交集

[编程题]区间列表交集
  • 热度指数:418 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定两个由闭区间组成的列表 first 和 second ,其中  。表示区间,保证这两个列表内部是不存在交集的,并且是排序之后的。

请找出两个区间列表的交集。

数据范围:区间列表的长度满足 , 区间列表中的值满足
示例1

输入

[[0,2],[5,10],[11,13]],[[1,3],[5,11]]

输出

[[1,2],[5,10],[11,11]]
import java.util.*;

// 比较优雅
public class Solution {

    public ArrayList<ArrayList<Integer>> intersectionofintervals (ArrayList<ArrayList<Integer>> first, ArrayList<ArrayList<Integer>> second) {
        // write your code here
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        int m = first.size(), n = second.size(), i = 0, j = 0;
        while (i < m && j < n) {
            // 没有交集 (循环至相交)
            while (i < m && j < n && (first.get(i).get(1) < second.get(j).get(0) || second.get(j).get(1) < first.get(i).get(0))) {
                if (first.get(i).get(1) < second.get(j).get(0)) i++;
                else j++;
            }
            if (i == m || j == n) break; // 越界
            // 取交集 (注意左右边界left、right取法)
            int left  = Math.max(first.get(i).get(0), second.get(j).get(0));
            int right = Math.min(first.get(i).get(1), second.get(j).get(1));
            res.add(new ArrayList<>(Arrays.asList(left, right)));
            if (first.get(i).get(1) == right)  i++; // 取到右端点了,下一个i
            if (second.get(j).get(1) == right) j++; // 取到右端点了,下一个j
        }

        return res;
    }
}

发表于 2025-04-12 20:53:59 回复(0)
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param first int整型ArrayList<ArrayList<>> 
     * @param second int整型ArrayList<ArrayList<>> 
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> intersectionofintervals(ArrayList<ArrayList<Integer>> first,
                                                                 ArrayList<ArrayList<Integer>> second) {

        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        // write code here
        int firstIndex = 0;
        int secondIndex = 0;

        while (firstIndex < first.size() && secondIndex < second.size()) {
            Integer firstStart = first.get(firstIndex).get(0);
            Integer firstEnd = first.get(firstIndex).get(1);

            Integer secondStart = second.get(secondIndex).get(0);
            Integer secondEnd = second.get(secondIndex).get(1);

            if (firstStart > secondEnd) {
                secondIndex++;
            } else if (firstEnd < secondStart) {
                firstIndex++;
            } else {
                ArrayList<Integer> temp = new ArrayList<>();
                temp.add(Math.max(firstStart, secondStart));
                if (firstEnd < secondEnd) {
                    temp.add(firstEnd);
                    firstIndex++;
                } else {
                    temp.add(secondEnd);
                    secondIndex++;
                }
                result.add(temp);
            }
        }
        return result;
    }
}

发表于 2022-04-14 23:09:09 回复(0)