福建路桥建设有限公司网站梧州论坛红豆思辨

2848、[简单] 与车相交的点

1、题目描述

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

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

2、解题思路

排序和合并区间：

• 首先对汽车坐标区间进行排序，使得区间按照起点从小到大排列。
• 然后，通过遍历排序后的区间来合并重叠的区间。
• 合并的过程是：如果当前区间的起点在已合并区间的终点之后，说明没有重叠，直接添加新的区间；否则，更新已合并区间的终点。

计算覆盖点数：

• 合并完所有区间后，计算每个合并后的区间所覆盖的整数点数，并累加到结果中。

3、代码实现

class Solution {
public:int numberOfPoints(vector<vector<int>>& nums) {if (nums.size() == 0) {return 0; // 如果没有汽车，返回0}vector<vector<int>> ans; // 用于存储合并后的区间sort(nums.begin(), nums.end()); // 按区间起点进行排序ans.push_back(nums[0]); // 将第一个区间加入结果集for (int i = 1; i < nums.size(); i++) {if (ans.back()[1] < nums[i][0]) {// 当前区间与最后一个合并区间不重叠，添加新的区间ans.push_back(nums[i]);} else {// 合并区间，更新终点ans.back()[1] = max(ans.back()[1], nums[i][1]);}}int ret = 0; // 结果变量for (const auto& v : ans) {// 计算每个合并后区间的覆盖点数ret += v[1] - v[0] + 1;}return ret; // 返回被覆盖的整数点数}
};

4、复杂度分析

• 时间复杂度：O(n log n)，主要是排序的时间复杂度，其中 n 是汽车的数量。
• 空间复杂度：O(n)，用于存储合并后的区间。