2
$\begingroup$

There are two sets of intervals provided to us.

target = {{11,13}, {7,10}, {0,3}, {6,6}}

space = {{10,12}, {2,6}, {4,8}, {0,4}, {9,10}}

I need to find the minimum number of intervals I can pick from the space set to ensure that all the intervals in the target set are intersected with.

Here, {2,6} and {10,12} intersect with each of the intervals in the target set. So, the minimum is 2.

My Attempts:

I tried to approach the problem by first sorting both the interval sets, and using a 2 pointer approach, but couldn't find a logic for minimization.

I also tried checking if the problem can be solved using Dynamic Programming. Once we sort the points, we can see what is the best set of intervals we can select that is optimal for our subproblem, which can help solve the larger problem. However, I haven't been able to come up with the state and transitions which would work.

The brute force logic is to try out all the subsets of space set and find the minimum size subset which intersects with all points, which I implemented in C++ and it works.

Code (brute-force):

#include<bits/stdc++.h>
using namespace::std;

bool doesIntersect(pair<int,int> p1, pair<int,int> p2) {
    return !(p1.first > p2.second || p1.second < p2.first);
}

int minIntervals(vector<pair<int,int>> target, vector<pair<int,int>> space) {
    int targetSize = target.size();
    int spaceSize = space.size();

    int minCount = INT_MAX;
    vector<pair<int,int>> subset;
    for (int i = 0 ; i < 1 << spaceSize ; i++) {
        subset.clear();
        for (int j = 0 ; j < spaceSize ; j++) {
            if (i & 1 << j) subset.push_back(space[j]);
        }

        set<int> s;
        for (int x = 0 ; x < subset.size() ; x++) {
            for (int y = 0 ; y < targetSize ; y++) {
                if (doesIntersect(subset[x], target[y])) s.insert(y);
            }
        }

        if (s.size() == targetSize) {
            minCount = min(minCount, (int) subset.size());
        }
    }

    return minCount;
}

int main() {
    vector<pair<int,int>> target = {{0,3}, {6,6}, {7,10}, {11,13}};
    vector<pair<int,int>> space = {{0,4}, {2,6}, {4,8}, {9,10}, {10,12}};
    cout << minIntervals(target, space) << "\n"; 
}

I want to understand approach/algorithms which can help me solve this problem with a much faster time complexity.

$\endgroup$
2
  • $\begingroup$ shouldn't intervals be denoted [a,b] or {a,..,b}? $\endgroup$
    – kodlu
    Commented May 8 at 17:01
  • $\begingroup$ Yes, I copied it right from the code. It should be [a,b] ideally $\endgroup$
    – Viktor
    Commented May 9 at 12:35

1 Answer 1

5
$\begingroup$

Of all intervals you need to cover, focus now on the one that ends earliest. This interval has to be covered, so take a covering interval that covers this interval, and that ends the latest. Pick that interval into the solution. Now, this interval might cover many intervals; delete all of them. Repeat.

$\endgroup$
2
  • 1
    $\begingroup$ It is worth noting that your simple greedy approach would give an optimal solution. $\endgroup$
    – codeR
    Commented May 8 at 8:39
  • $\begingroup$ Thanks, this is great. I’ll try writing a program for it. It’s the deletion that might be costly. Will try using a bit mask to mark deletion. $\endgroup$
    – Viktor
    Commented May 9 at 12:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.