Found this problem to which, I could not find any simple solution. But thinking about the question found this very simple solution, hence sharing.

Problem Statement

Given a number and intervals, find all intervals having that number effectively. Imagine the method is being called thousands of times.
Example Input
Intervals -> [{1, 10}, {8, 12}, {3, 5}, {15,20}]
Queries -> [5, 10, 18]
For query 1 -> 5 lies inside {1, 10} and {3, 5}, hence answer to this query is 2.
Similarly for query 2 -> 10 lies inside {1, 10} and {8, 12}, hence answer to this query is 2.
And for query 3 -> 18 lies inside {15, 20} only, hence answer to this query is 1.

Existing Solution

Most of the time I was thinking about, how to count which of the interval contain the required number. Turns out this is quite computation heavy. We can use prefix-sum method which fails when the intervals are large. Using Interval tree is quite complex as well.

Solution

Lets start thinking the opposite way, lets count the intervals that don't contain the number. How will we do that?

• We will maintain 2 int arrays.
  • First, say st will contain the interval start.
  • Second en will contain the interval end.
• We sort them.
• Now for every query we ask the 2 arrays.
  • Array st, give me the number of startings after the number. Can be done in log(n) with upper_bound.
  • Array en, give me the number of endings before the number. Can be done in log(n) with lower_bound.
• Now the ans to the quesy is n - (sum of these questions)

Code

vector<int> solution(vector<vector<int>> &v, vector<int> queries){
    int n = v.size(), q = queries.size();
    vector<int> st, en;
    vector<int> res;
    for(int i = 0; i < n; ++i) {
        st.push_back(v[i][0]);
        en.push_back(v[i][1]);
    }
    sort(st.begin(), st.end());
    sort(en.begin(), en.end());
    
    for(int i = 0; i < q; ++i) {
        int cur = queries[i];
        int before = lower_bound(en.begin(), en.end(), cur) - en.begin();
        int after = st.end() - upper_bound(st.begin(), st.end(), cur);
        int qres = n - before - after;
        res.push_back(qres);
    }
    return res;
}

Let me know if you have edge cases that this solution might miss, in the comments.