#include <iostream>
#include <string>
#include <vector>
using namespace std;
pair<int, int> getMinMax(vector<pair<int, int>> intervals)
{
int min, max = 0;
min = intervals[0].first;
max = intervals[0].second;
int startIndex = 0;
int endIndex = 0;
for (int i = 1; i < intervals.size(); ++i)
{
// find the largest minimum
if (intervals[i].first > min)
{
min = intervals[i].first;
endIndex = i;
}
// find the smallest maximum
if (intervals[i].second < max)
{
max = intervals[i].second;
startIndex = i;
}
}
return pair<int, int>(startIndex, endIndex);
}
// Given a set of closed intervals, find the smallest set of numbers that covers all the intervals.
// If there are multiple smallest sets, return any of them.
// For example, given the intervals[0, 3], [2, 6], [3, 4], [6, 9], one set of numbers that covers all these intervals is{ 3, 6 }.
pair<int, int> getInterval(vector<pair<int, int>> intervals)
{
//find extremities
pair<int,int> extremes = getMinMax(intervals);
int startIndex = extremes.first;
int endIndex = extremes.second;
// we want to use the largest start value and
// the smallest end value to define our range
return pair<int, int>(intervals[startIndex].second, intervals[endIndex].first);
}
int main()
{
vector<pair<int, int>> intervals;
// construct intervals
intervals.push_back(pair<int, int>(0, 3));
intervals.push_back(pair<int, int>(2, 6));
intervals.push_back(pair<int, int>(3, 4));
intervals.push_back(pair<int, int>(6, 9));
auto result = getInterval(intervals);
cout << "Mimimum Spanning Interval: [" << result.first << ", " << result.second << "]" << endl;
return 0;
}
Comments