The Interval Covering Problem

EPI 18.3

Description:

Example:

Given task time {[0,3], [2,6], [3,4], [6,9]}

return 3, 9

Answer is not unique

Idea:

Greedy.

1. sort based on the right value
2. take current right value as last_visit_time, if it cannot cover next interval, update it to the next interval's right value

Time O(n)

Code:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Interval{
    int left, right;
    Interval(int l, int r): left(l), right(r) {}
};

vector<int> intervalCovering(vector<Interval> arr){
    sort(arr.begin(), arr.end(), [](const Interval & a, const Interval & b)->bool {return a.right<b.right; } );

    int lastTime=arr[0].right;
    vector<int> result;
    result.push_back(lastTime);

    for(int i=1; i< arr.size(); i++){
        if(arr[i].left>lastTime){
            lastTime=arr[i].right;
            result.push_back(lastTime);
        }
    }
    return result;
}

int main(){
    vector<Interval> arr;
    arr.push_back(Interval(0, 3));
    arr.push_back(Interval(2, 6));
    arr.push_back(Interval(3, 4));
    arr.push_back(Interval(6, 9));

    for(auto elem: intervalCovering(arr)){
        cout<<elem<<' ';
    }
}