What is the easiest way to solve Points That Intersect With Cars?

The easiest solution is to mark every integer point covered by each car using a boolean array or hash set, then count the marked positions. It works especially well because all coordinates are between 1 and 100.

Why does interval merging work for this problem?

Merging works because overlapping car ranges cover one continuous block of integer points. After sorting by start, you can combine overlaps and add each merged block length once, which avoids double-counting.

Is prefix sum overkill for this problem?

It is not necessary for the given limits, but it is still a valid and neat approach. It becomes more interesting when you want to count coverage from many intervals or extend the task to coverage frequency.

What is the main failure mode in this pattern?

The main failure mode is double-counting points that belong to multiple overlapping cars. Another common mistake is forgetting that both start and end are included in the covered segment.

How does the array scanning plus hash lookup pattern apply here?

You scan each interval in nums and insert every covered integer point into a set, or mark it in a boolean array. The lookup structure guarantees each point is counted once even when intervals overlap heavily.

#2848

Easy

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

与车相交的点

给你一个下标从 0 开始的二维整数数组 nums 表示汽车停放在数轴上的坐标。对于任意下标 i ， nums[i] = [start i , end i ] ，其中 start i 是第 i 辆车的起点， end i 是第 i 辆车的终点。返回数轴上被车任意部分覆盖的整数点的数目。示例 1：…

数组哈希表前缀和

题目描述

给你一个下标从 0 开始的二维整数数组 nums 表示汽车停放在数轴上的坐标。对于任意下标 i，nums[i] = [start_i, end_i] ，其中 start_i 是第 i 辆车的起点，end_i 是第 i 辆车的终点。

返回数轴上被车 任意部分 覆盖的整数点的数目。

示例 1：

输入：nums = [[3,6],[1,5],[4,7]]
输出：7
解释：从 1 到 7 的所有点都至少与一辆车相交，因此答案为 7 。

示例 2：

输入：nums = [[1,3],[5,8]]
输出：7
解释：1、2、3、5、6、7、8 共计 7 个点满足至少与一辆车相交，因此答案为 7 。

提示：

1 <= nums.length <= 100
nums[i].length == 2
1 <= start_i <= end_i <= 100

lightbulb

解题思路

方法一：差分数组

根据题目描述，我们需要给每个区间 $[\textit{start}_i, \textit{end}_i]$ 增加一个车辆，我们可以使用差分数组来实现。

我们定义一个长度为 $102$ 的数组 $d$ ，对于每个区间 $[\textit{start}_i, \textit{end}_i]$ ，我们将 $d[\textit{start}_i]$ 加 $1$ ，将 $d[\textit{end}_i + 1]$ 减 $1$ 。

最后，我们对 $d$ 进行前缀和运算，统计前缀和大于 $0$ 的个数即可。

时间复杂度 $O(n + m)$ ，空间复杂度 $O(m)$ ，其中 $n$ 是给定数组的长度，而 $m$ 是数组中的最大值，本题中 $m \leq 102$ 。

1

2

3

4

5

6

7

8

9

class Solution:
    def numberOfPoints(self, nums: List[List[int]]) -> int:
        m = 102
        d = [0] * m
        for start, end in nums:
            d[start] += 1
            d[end + 1] -= 1
        return sum(s > 0 for s in accumulate(d))

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The small coordinate bound up to 100 is a strong signal that brute-force marking each integer point is fully acceptable.
question_mark
If the interviewer mentions overlap removal or sorting by the first element, they are steering toward interval merging.
question_mark
If they ask for a cleaner counting trick instead of repeated point insertion, they may want the Prefix Sum difference-array version.

warning

常见陷阱

外企场景

error
Forgetting that intervals are inclusive causes off-by-one errors, especially when computing merged length as end - start + 1.
error
Double-counting overlap happens when you sum each car length independently instead of merging or deduplicating points.
error
Using endi + 1 in the prefix method without allocating enough space can break the last update boundary.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Return the actual covered points instead of only the count, which favors the marking approach.
arrow_right_alt
Increase coordinate bounds dramatically, which makes sort-and-merge more practical than point-by-point scanning.
arrow_right_alt
Ask how many points are covered by at least k cars, which turns the Prefix Sum running count into the key extension.

help

常见问题

外企场景

继续练习

#2845 统计趣味子数组的数目 #2875 无限数组的最短子数组 #3026 最大好子数组和