LeetCode 986. 区间列表的交集

Categories:

题目描述
思路分析
1. 解法一：双指针扫描（推荐）
相似题目

题目描述

✅ 986. 区间列表的交集

思路分析

解法一：双指针扫描（推荐）

核心思路：

两个指针分别遍历两个区间列表。

当前交集为 max(start) 与 min(end)。

谁的结束位置更小，就移动谁。

复杂度分析：

时间复杂度：O(m + n)，其中 m、n 分别为两个列表长度。

空间复杂度：O(1)，除结果外仅使用常数额外空间。

class Solution {
    public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
        int i = 0;
        int j = 0;
        List<int[]> res = new ArrayList<>();

        // 双指针同步扫描
        while (i < firstList.length && j < secondList.length) {
            int start = Math.max(firstList[i][0], secondList[j][0]);
            int end = Math.min(firstList[i][1], secondList[j][1]);

            if (start <= end) {
                res.add(new int[]{start, end});
            }

            if (firstList[i][1] < secondList[j][1]) {
                i++;
            } else {
                j++;
            }
        }

        return res.toArray(new int[res.size()][]);
    }
}

func intervalIntersection(firstList [][]int, secondList [][]int) [][]int {
	res := make([][]int, 0)
	i, j := 0, 0

	// 双指针同步扫描
	for i < len(firstList) && j < len(secondList) {
		start := max(firstList[i][0], secondList[j][0])
		end := min(firstList[i][1], secondList[j][1])

		if start <= end {
			res = append(res, []int{start, end})
		}

		if firstList[i][1] < secondList[j][1] {
			i++
		} else {
			j++
		}
	}

	return res
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

相似题目

题目	难度	考察点
56. 合并区间	中等	区间合并
57. 插入区间	中等	区间合并
435. 无重叠区间	中等	贪心
452. 用最少数量的箭引爆气球	中等	区间贪心
1288. 删除被覆盖区间	中等	区间排序

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/71305127