2848.points-that-intersect-with-cars.md

2848. Points That Intersect With Cars

Brute Force

We maintain a set of points, then add points that are covered by each interval.

fun numberOfPoints(nums: List<List<Int>>): Int {
    val points = HashSet<Int>()
    for (num in nums) {
        val start = num[0]
        val end = num[1]
        for (i in start..end) {
            points.add(i)
        }
    }
    return points.size
}

• Time Complexity: O(n * C) where n is the size of the list and C is the range of interval values.
• Space Complexity: O(C).

Interval Intersection

Given two intervals, the points that intersect with both intervals are the points in the intersection of the two intervals. We use the same approach of 56. Merge Intervals to solve this problem. We sort the intervals by the start point, merge the intervals that overlap with each other and count the number of points that are covered by the merged intervals.

fun numberOfPoints(list: List<List<Int>>): Int {
    val nums = list.sortedBy { it[0] }
    var merged = nums[0]
    var covered = 0
    for (i in 1 until nums.size) {
        val toMerge = nums[i]
        if (overlapped(merged, toMerge)) {
            merged = listOf(
                minOf(merged[0], toMerge[0]), 
                maxOf(merged[1], toMerge[1])
            )
        } else {
            covered += merged[1] - merged[0] + 1
            merged = toMerge
        }
    }
    covered += merged[1] - merged[0] + 1
    return covered
}

• Time Complexity: O(n * log(n)) where n is the size of the list.
• Space Complexity: O(n).

Line Sweep

fun numberOfPoints(nums: List<List<Int>>): Int {
    val n = nums.size
    // We find the nearest and farest end point.
    val min = nums.minOf { it[0] }
    val max = nums.maxOf { it[1] }
    // Create a difference array from 0 to max + 1. (max + 1 for end + 1)
    val diff = IntArray(max + 1 + 1)
    for (num in nums) {
        val (start, end) = num
        diff[start] += 1
        diff[end + 1] -= 1
    }
    var points = 0
    var value = 0
    // Iterate all possible points from 0 to max.
    for (i in 0..max) {
        value += diff[i]
        if (value > 0) points++
    }
    return points
}

// Or equivalently, we find the specific ranges of the intervals.
fun numberOfPoints(nums: List<List<Int>>): Int {
    val n = nums.size
    val min = nums.minOf { it[0] }
    val max = nums.maxOf { it[1] }
    val diff = IntArray(max - min + 1 + 1) // +1 for 0 ~ n, another +1 for max + 1 (end + 1)
    for (num in nums) {
        val (start, end) = num
        // Remember to offset the start and end points.
        diff[start - min] += 1
        diff[end - min + 1] -= 1
    }
    var points = 0
    var value = 0
    for (v in diff) {
        value += v
        if (value > 0) points++
    }
    return points
}

• Time Complexity: O(n + max) where n is the size of the list and max is the maximum end point.
• Space Complexity: O(max).