Algorithm to Count Intervals Intersecting at Point

You are given a two-dimensional list of integers intervals and an integer point. Each element contains [start, end] represents an inclusive interval.

Return the number of intervals that are intersecting at point.

Constraints
n ≤ 100,000 where n is the length of intervals
Example 1
Input

1 2 3 4 5 6

intervals = [     [1, 5],     [3, 9],     [4, 8],     [10, 13] ]

intervals = [
    [1, 5],
    [3, 9],
    [4, 8],
    [10, 13]
]

point = 4
Output
3
Explanation
At time 4, there are 3 intervals that are intersecting: [1, 5], [3, 9], [4, 8]

C++ Algorithm to Count Intervals Intersecting at Point

Iterating all the intervals and count if it the point falls in it. This takes O(N) time and we can just implement it using a simple loop:

1
2
3
4
5
6
7

int countIntervals(vector<vector<int>>& intervals, int point) {
    int ans = 0;
    for (auto &e: intervals) {
        if (e[0] <= point && e[1] >= point) ans ++;
    }
    return ans;
}

int countIntervals(vector<vector<int>>& intervals, int point) {
    int ans = 0;
    for (auto &e: intervals) {
        if (e[0] <= point && e[1] >= point) ans ++;
    }
    return ans;
}

We can avoid using the for-loop via the STL::count_if.

1
2
3
4
5

int countIntervals(vector<vector<int>>& intervals, int point) {
    return count_if(begin(intervals), end(intervals), [&](auto &e) {
        return (e[0] <= point && e[1] >= point);
    });
}

int countIntervals(vector<vector<int>>& intervals, int point) {
    return count_if(begin(intervals), end(intervals), [&](auto &e) {
        return (e[0] <= point && e[1] >= point);
    });
}

Python Algorithm to Count Intervals Intersecting at Point

In Python, we can do this using one-liner to count the intersecting intervals:

1
2
3

class Solution:
    def solve(self, intervals, point):
        return sum(a >= point and point <= b for a, b in intervals)

class Solution:
    def solve(self, intervals, point):
        return sum(a >= point and point <= b for a, b in intervals)

See also: Bruteforce or Line Sweep Algorithms to Remove Covered Intervals

–EOF (The Ultimate Computing & Technology Blog) —