与车相交的点

2024-09-15

题目:

给你一个下标从 0 开始的二维整数数组 nums 表示汽车停放在数轴上的坐标。对于任意下标 inums[i] = [starti, endi] ,其中 starti 是第 i 辆车的起点,endi 是第 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 <= starti <= endi <= 100

思路:

先将 nums 按照起点大小进行排序
然后将有交叉区间的数组进行合并
最后统计不交叉区间一共覆盖多少点即可

代码:

class Solution {
public:
    static bool cmp(const vector<int>& a, const vector<int>& b) {
        return a[0] < b[0];
    }
    int numberOfPoints(vector<vector<int>>& nums) {
        sort(nums.begin(), nums.end(), cmp);
        vector<vector<int>> temp;
        for (int i = 0; i < nums.size(); i++) {
            if (temp.size() == 0) {
                temp.push_back(nums[i]);
                continue;
            }
            if (nums[i][0] <= temp.back()[1]) temp.back()[1] = max(temp.back()[1], nums[i][1]);
            else temp.push_back(nums[i]);
        }
        int ans = 0;
        for (int i = 0; i < temp.size(); i++) {
            ans += (temp[i][1] - temp[i][0] + 1);
        }
        return ans;
    }
};