C++ | Find smallest interval
Problem Statement : Given a number 'n', and set of 'n' closed intervals. Find the smallest interval that covers all the intervals. If there are many, return any of them.
For example : n = 5
intervals = [0,3],[2,6],[3,4],[6,9],
in this case the resultant interval would be = [3,6], as is the smallest interval that covers all the interval
Following is the C++ implementation of above problem :
using namespace std;
pair<int,int> findSmallestSet(vector<pair<int,int> > v) {
pair<int,int> ret = {INT_MAX, INT_MIN};
for(int i = 0; i < (int)v.size(); i++) {
if(v[i].first > ret.second) {
ret.second = v[i].first;
}
if(v[i].second < ret.first) {
ret.first = v[i].second;
}
}
return ret;
}
int main() {
cout << "Enter the number of intervals : ";
int n;
cin >> n;
cout << "Enter the start and end of each interval : ";
vector<pair<int,int> > v(n);
for(int i = 0; i < n; i++) {
cin >> v[i].first >> v[i].second;
}
auto smallestSet = findSmallestSet(v);
cout << "The smallest interval is : ";
cout << smallestSet.first << " " << smallestSet.second << '\n';
return 0;
}
Input and Output :
Comments