与车相交的点

You are given a 0-indexed 2D integer array nums representing the coordinates of the cars parking on a number line. For any index i, nums[i] = [starti, endi] where starti is the starting point of the ith car and endi is the ending point of the ith car.

Return the number of integer points on the line that are covered with any part of a car.

 

Example 1:

Input: nums = [[3,6],[1,5],[4,7]]
Output: 7
Explanation: All the points from 1 to 7 intersect at least one car, therefore the answer would be 7.

Example 2:

Input: nums = [[1,3],[5,8]]
Output: 7
Explanation: Points intersecting at least one car are 1, 2, 3, 5, 6, 7, 8. There are a total of 7 points, therefore the answer would be 7.

 

Constraints:

• 1 <= nums.length <= 100
• nums[i].length == 2
• 1 <= starti <= endi <= 100

/*
 * 题目思路：
 * 给定一个二维整数数组，表示数轴上的多个区间。每个区间[start_i, end_i]表示第i辆车的起点和终点。
 * 需要计算出这些区间在数轴上覆盖的所有整数点的总数。
 * 使用Java Stream：
 * 1. 使用一个Set来存储所有覆盖的点。
 * 2. 遍历每个区间，添加范围内的点到Set中。
 * 3. 返回Set的大小。
 */

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
import java.util.stream.IntStream;

public class Solution {
    public int countCoveredPoints(int[][] nums) {
        Set<Integer> coveredPoints = new HashSet<>();
        Arrays.stream(nums).forEach(interval ->
            IntStream.rangeClosed(interval[0], interval[1]).forEach(coveredPoints::add)
        );
        return coveredPoints.size();
    }
}

此题解采用了区间合并的策略来计算被至少一辆车覆盖的整数点的总数。首先，对输入的区间数组nums进行排序，以保证区间的起点是递增的。然后，使用一个变量m来维护当前正在合并的区间。遍历排序后的数组，对于每个区间，如果它的起点在当前合并区间m的终点之前或恰好相等，则将其与m进行合并，即更新m的终点为当前区间终点和m终点的较大者。如果新区间的起点在m的终点之后，说明没有重叠部分，当前m区间的计算可以结束，并将其长度加到答案中，然后用新区间更新m。遍历结束后，将最后一个区间的长度也加到答案中。

O(n log n)

O(n)