CODEWITHSUNDEEP
algorithmintervals
codewarrior
codewarrior

Reputation: 1034

Find coverage of a set of intervals

I came across this question while preparing for an interview long back and thought it was an interesting problem to solve. The problem is this: Find the coverage of a set of intervals For example - given [1,4), [-2,3), [9,10) : the output should be 7 (the set of intervals cover -2,-1,0,1,2,3,9).

My initial approach was to iterate over the set of intervals; add the number in each interval to a Sorted Linked list. If any number already exists in the sorted list, skip it. I believe this takes O(N^2) time and consumes O(N) space, so we could probably do better.

Alternately, we could use an Interval BST. However, that seems to be primarily used for finding out if there is an overlap with a given interval (which takes O(lgn)). Finding the coverage of it would seem to take O(n^2) again. Can we do better than O(n^2)?

Upvotes: 1

Views: 1273

Answers (1)

Pavel
Pavel

Reputation: 1

You can look at them as pairs and sort them by the first element.

After sorting you'll have : {<-2, 2>, <1,3>, <9, 9>}.

Sorting will take O(NlogN).

Now make a variable sum = 0.

Then set L = (1).left and R = (1).right.

Linearly traverse everything keeping the largest R you've encountered until R < (k).left, then do sum += abs(L - R) + 1 and proceed for the rest as just described. This will take about O(N). So, altogether : O(NlogN + N) ~ O(NlogN).

The space is also linear.

#include <iostream>
#include <algorithm>
#include <vector>
#include <climits>

using namespace std;
typedef pair<int, int> pii;

int main() {
    int l, r;
    vector<pii> pairs;
    while (cin >> l >> r) {
        pairs.emplace_back(l, r);
    }
    pairs.emplace_back(INT_MAX, INT_MAX); // sentinel
    sort(pairs.begin(), pairs.end(), 
    [](const pii& x, const pii& y) { return x.first < y.first; });

    auto p_one = pairs.begin(), p_two = pairs.begin() + 1;
    int L = p_one->first;
    int R = p_one->second;
    int sum = 0;
    while (p_two != pairs.end()) {
        if (R < p_two->first) {
            sum += abs(L - R) + 1;
            L = p_two->first;
            R = INT_MIN;
        }
        p_one++; p_two++;
        if (p_one->second > R) R = p_one->second;
    }
    cout << sum;
}

P.S. I haven't fully tested the code, but it seems to work.

Upvotes: 2

Related Questions