Efficiently count occurrences of each element from given ranges

Question

So i have some ranges like these:

2 4
1 9
4 5
4 7

For this the result should be

1 -> 1
2 -> 2
3 -> 2
4 -> 4
5 -> 3  
6 -> 2
7 -> 2
8 -> 1
9 -> 1

The naive approach will be to loop through all the ranges but that would be very inefficient and the worst case would take O(n * n)

What would be the efficient approach probably in O(n) or O(log(n))

Answer 1

Here's the solution, in O(n):

The rationale is to add a range [a, b] as a +1 in a, and a -1 after b. Then, after adding all the ranges, then compute the accumulated sums for that array and display it.

If you need to perform queries while adding the values, a better choice would be to use a Binary Indexed Tree, but your question doesn't seem to require this, so I left it out.

#include <iostream>
#define MAX 1000
using namespace std;

int T[MAX];

int main() {
    int a, b;
    int min_index = 0x1f1f1f1f, max_index = 0;
    while(cin >> a >> b) {
        T[a] += 1;
        T[b+1] -= 1;
        min_index = min(min_index, a);
        max_index = max(max_index, b);
    }

    for(int i=min_index; i<=max_index; i++) {
        T[i] += T[i-1];   
        cout << i << " -> " << T[i] << endl;
    }
}

UPDATE: Based on the "provocations" (in a good sense) by גלעד ברקן, you can also do this in O(n log n):

#include <iostream>
#include <map>
#define ull unsigned long long
#define miit map<ull, int>::iterator
using namespace std;

map<ull, int> T;

int main() {
    ull a, b;
    while(cin >> a >> b) {
        T[a] += 1;
        T[b+1] -= 1;
    }

    ull last;
    int count = 0;
    for(miit it = T.begin(); it != T.end(); it++) {
        if (count > 0)
            for(ull i=last; i<it->first; i++)
                cout << i << " " << count << endl;
        count += it->second;
        last = it->first;
    }
}

The advantage of this solution is being able to support ranges with much larger values (as long as the output isn't so large).

Answer 2

Paul's answer still counts from "the first item that is at any range and iterate[s] over all numbers to the last element that is in any range." But what is we could aggregate overlapping counts? For example, if we have three (or say a very large number of) overlapping ranges [(2,6),[1,6],[2,8] the section (2,6) could be dependent only on the number of ranges, if we were to label the overlaps with their counts [(1),3(2,6),(7,8)]).

Using binary search (once for the start and a second time for the end of each interval), we could split the intervals and aggregate the counts in O(n * log m * l) time, where n is our number of given ranges and m is the number of resulting groups in the total range and l varies as the number of disjoint updates required for a particular overlap (the number of groups already within that range). Notice that at any time, we simply have a sorted list grouped as intervals with labeled count.

2 4
1 9
4 5
4 7

=>

(2,4)
(1),2(2,4),(5,9)
(1),2(2,3),3(4),2(5),(6,9)
(1),2(2,3),4(4),3(5),2(6,7),(8,9)

Answer 3

The solution would be pretty simple:

1. generate two lists with the indices of all starting and ending indices of the ranges and sort them.
2. Generate a counter for the number of ranges that cover the current index. Start at the first item that is at any range and iterate over all numbers to the last element that is in any range. Now if an index is either part of the list of starting-indices, we add 1 to the counter, if it's an element of the ending-indices, we substract 1 from the counter.

Implementation:

vector<int> count(int** ranges , int rangecount , int rangemin , int rangemax)
{
    vector<int> res;

    set<int> open, close;

    for(int** r = ranges ; r < ranges + sizeof(int*) * rangecount ; r++)
    {
        open.add((*r)[0]);
        close.add((*r)[1]);
    }

    int rc = 0;

    for(int i = rangemin ; i < rangemax ; i++)
    {
        if(open.count(i))
            ++rc;

        res.add(rc);

        if(close.count(i))
            --rc;
    }

    return res;
}

Answer 4

So you want the output to be an array, where the value of each element is the number of input ranges that include it?

Yeah, the obvious solution would be to increment every element in the range by 1, for each range.

I think you can get more efficient if you sort the input ranges by start (primary), end (secondary). So for 32bit start and end, start:end can be a 64bit sort key. Actually, just sorting by start is fine, we need to sort the ends differently anyway.

Then you can see how many ranges you enter for an element, and (with a pqueue of range-ends) see how many you already left.

# pseudo-code with possible bugs.
# TODO: peek or put-back the element from ranges / ends
 # that made the condition false.

pqueue ends;    // priority queue
int depth = 0;  // how many ranges contain this element
for i in output.len {
    while (r = ranges.next && r.start <= i) {
        ends.push(r.end);
        depth++;
    }
    while (ends.pop < i) {
        depth--;
    }
    output[i] = depth;
}
assert ends.empty();

Actually, we can just sort the starts and ends separately into two separate priority queues. There's no need to build the pqueue on the fly. (Sorting an array of integers is more efficient than sorting an array of structs by one struct member, because you don't have to copy around as much data.)