Question

2848. Points That Intersect With Cars

中文文档

Description

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

Solutions

Solution 1: Difference Array

We create a difference array $d$ of length $110$, then traverse the given array. For each interval $[a, b]$, we increase $d[a]$ by $1$ and decrease $d[b + 1]$ by $1$. Finally, we traverse the difference array $d$, calculate the prefix sum $s$ at each position. If $s > 0$, it means that the position is covered, and we increase the answer by $1$.

The time complexity is $O(n)$, and the space complexity is $O(M)$. Here, $n$ is the length of the given array, and $M$ is the maximum value in the array.

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

class Solution {
  public int numberOfPoints(List<List<Integer>> nums) {
    int[] d = new int[110];
    for (var e : nums) {
      d[e.get(0)]++;
      d[e.get(1) + 1]--;
    }
    int ans = 0, s = 0;
    for (int x : d) {
      s += x;
      if (s > 0) {
        ans++;
      }
    }
    return ans;
  }
}

class Solution {
public:
  int numberOfPoints(vector<vector<int>>& nums) {
    int d[110]{};
    for (auto& e : nums) {
      d[e[0]]++;
      d[e[1] + 1]--;
    }
    int ans = 0, s = 0;
    for (int x : d) {
      s += x;
      ans += s > 0;
    }
    return ans;
  }
};

func numberOfPoints(nums [][]int) (ans int) {
  d := [110]int{}
  for _, e := range nums {
    d[e[0]]++
    d[e[1]+1]--
  }
  s := 0
  for _, x := range d {
    s += x
    if s > 0 {
      ans++
    }
  }
  return
}

function numberOfPoints(nums: number[][]): number {
  const d: number[] = Array(110).fill(0);
  for (const [a, b] of nums) {
    d[a]++;
    d[b + 1]--;
  }
  let ans = 0;
  let s = 0;
  for (const x of d) {
    s += x;
    if (s > 0) {
      ans++;
    }
  }
  return ans;
}