Find smallest set of numbers that covers all intervals

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}.

Example:

Input:  intervals=  {{0,3},{2,6},{3,4},{6,9}}
Output: [3, 6]

Approach

C++

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

vector<intfindCoveringInterval(vector<vector<int>> &intervals)
{
    int smallMax = INT_MAX, largeMin = INT_MIN;
    for (int i = 0; i < intervals.size(); i++)
    {
        smallMax = min(smallMax, intervals[i][1]);
        largeMin = max(largeMin, intervals[i][0]);
    }

    vector<int> res;
    res.push_back(smallMax);
    res.push_back(largeMin);
    sort(res.begin(), res.end());

    return res;
}

int main()
{
    vector<vector<int>> intervals = {{03}, {26}, {34}, {69}};

    vector<int> res = findCoveringInterval(intervals);

    cout << "[";
    cout << res[0] << ", " << res[1];
    cout << "]";

    return 0;
}


No comments:

Post a Comment