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.
