Interval Scheduling

Problem Statement: Given a set of intervals with a start and end time, as well as a corresponding value for profit that does not vary among the intervals, find the maximum amount of profit that one can make - without overlapping any schedules.

Greedy Algorithm

1. Select the interval, x, with the earliest finishing time.

2. Remove x, and all intervals intersecting x, from the set of candidate intervals.

3. Continue until the set of candidate intervals is empty.

Example

Implementation 1

Time Complexity: O(nlogn)+ O(n^2)

using Interval = pair<int, int>;

void print_intervals(vector<Interval> &intervals )
{
    for (const auto& p : intervals)
        cout << p.first << ", " << p.second << endl;
    cout << endl;
}

vector<Interval> max_intervals(vector<Interval> &intervals)
{
    sort(intervals.begin(), intervals.end(), [](Interval &left, Interval &right) {
        return left.second < right.second;
    });

    vector<Interval> compat_i;
    for (int i = 0; i < intervals.size(); i++) {
        int cur_early = intervals[i].second;
        compat_i.push_back(intervals[i]);

        // skip noncompatable intervals
        int j = i + 1;
        for (; j < intervals.size(); j++) {
            if (cur_early > intervals[j].first)
                continue;
            else break;
        }
        i = j - 1;
    }

    return compat_i;
}

int main()
{
    vector<pair<int, int>> intervals = { {1,4},{ 3,5 },{ 0,6 },
                                 { 4,7 },{ 3,8 },{ 5,9 },
                                 { 6,10 },{ 8,11 } };

    vector<pair<int, int>> m_intervals = max_intervals(intervals);
    print_intervals(m_intervals);
}

Implementation 2

Time Complexity: O(n + nlogn)

The Idea: Since all the intervals are uni-weight, the intuition is to maximize the amount of intervals that can fit within the allotted time frame. By sorting the intervals by earliest finish, we guarantee that every successive interval is either going to cross with the current interval, or not thereby eliminating intervals from appearing before. That means that the first intervals is always guaranteed to be in the set (as one possible solution) because either 1) no intervals cross with the first interval (and so it should be added to the collective set), or 2) a set of intervals do cross over, but in everyone of these intervals there is guaranteed to only be a maximum of one valid interval (or more if proceeding intervals have the same end time - but because these are uni-weight interval will do). In the general case however, selecting an interval that has a greater end time than the first interval means that we could potentially be getting rid of even more intervals that the first interval would have not gotten rid of. So the first interval minimize the number of intervals removed and hence the most opportunity for proceeding intervals to added into the set. We can apply this argument inductively for every successive interval.

struct Schedule {
    Schedule(int start, int end, int id) :
        start(start), end(end), id(id) {}

    int start, end, id;
};

vector<Schedule> uni_weight_max_scheduling(vector<Schedule> schedules) {

    sort(schedules.begin(), schedules.end(),
        [](const Schedule & a, const Schedule & b) {
        return a.end < b.end;
    });

    vector<Schedule> most_schedules;
    most_schedules.push_back(schedules.front());

    for (auto &s : schedules) {
        if (s.start >= most_schedules.back().end) {
            most_schedules.push_back(s);
        }
    }

    return most_schedules;
}


int main()
{
    vector<Schedule> schedules =
        { { 1,4,0 },{ 3,5,1 },{ 0,6,3 },{ 4,7,4 },
        { 3,8,5 },{ 5,9,6 },{ 6,10,7 },{ 8,11,8 } };

    vector<Schedule> max_schedules = uni_weight_max_scheduling(schedules);
    for (auto s : max_schedules)
        cout << "(" << s.start << ", " << s.end << ")" << endl;
}

Output

(1, 4)
(4, 7)
(8, 11)

Problem Statement: Given a set of intervals with a start and end time, as well as a corresponding value for profit that does vary among the intervals, find the maximum amount of profit that one can make - without overlapping any schedules.

Assuming the same example from before, where the weight for each schedule is proportional to their duration or (end - start) times

Dynamic Programming Algorithm

1. Sort intervals by earliest finish time.

2. Compute array P[]

   1. For every i in P[], compute P[i] to be the latest valid schedule that appears before it.

   2. Using binary search, the latest valid schedule is guaranteed when (1) the end time appears before it's start time, and (2) the schedule that appears after has an end time that appears after it's start time.

3. Compute OPT[]

   1. For every i in OPT[], compute OPT[i] to be the value of maximum profit between subset of intervals [0,i].

   2. OPT[i] = max(schedules[i - 1].weight + OPT[subset_latest_valid[i-1]], OPT[i - 1]);

      1. The first weight OPT[0] will always be 0, as a placeholder to build off from.

      2. Building up linearly, a interval is either included or not included into the set. The current interval is included in the set if, its current weight schedules[i - 1].weight along with the collective weight of its previous set of intervals OPT[subset_latest_valid[i-1]] manage to exceed the previous optimal OPT[i - 1].

Assuming the same example from before, where the weight for each schedule is proportional to their duration or (end - start) times

OPT[n]:

0: 0
1: 3
2: 3
3: 6
4: 6
5: 6
6: 7
7: 10
8: 10

Time Complexity: O(nlogn + nlogn + n)

The Idea:

struct Schedule {
    Schedule(int start, int end) :
        start(start), end(end), weight(end - start) {}

    int start, end, weight;
};


int binary_search(const vector<Schedule> &schedules, int low, int high, int current) {
    if (low > high) return 0;

    int mid = ((high - low) / 2) + low;

    if (schedules[mid].end <= schedules[current].start) {
        if (schedules[mid + 1].end <= schedules[current].start)
            return binary_search(schedules, mid + 1, high, current);
        else return mid + 1;
    }

    else return binary_search(schedules, low, mid - 1, current);

}

int find_latest_schedule(const vector<Schedule> &schedules, int current) {
    return binary_search(schedules, 0, current - 1, current);
}

vector<int> computeP(const vector<Schedule> &schedules) {
    vector<int> p(schedules.size(), 0);

    for (int i = 1; i < p.size(); i++)
        p[i] = find_latest_schedule(schedules, i);

    return p;
}

int interval_scheduling(vector<Schedule> schedules) {

    if (schedules.empty()) return 0;

    sort(schedules.begin(), schedules.end(),
        [](const Schedule & a, const Schedule & b) {
        return a.end < b.end;
    });

    vector<int> subset_latest_valid = computeP(schedules);
    vector<int> OPT(schedules.size()+1, 0);
    for (int i = 1; i < OPT.size(); i++)
        OPT[i] = max(schedules[i - 1].weight + OPT[subset_latest_valid[i-1]], OPT[i - 1]);

    return OPT.back();

}


int main()
{
    vector<Schedule> schedules =
        { { 1,4 },{ 3,5 },{ 0,6 },{ 4,7 },
        { 3,8 },{ 5,9 },{ 6,10 },{ 8,11 } };

    cout << interval_scheduling(schedules) << endl;

}

Trace-back to Find Solution

Moving backwards, an interval is selected if it's own weight and the optimal solution of its previous neighbors exceed the optimal amount at OPT[j]. If so, the next interval must at least follow from its own previous valid interval P[j]. Otherwise, observe the previously adjacent interval.

void trace_back_intervals(const vector<Schedule> &schedules, const vector<int> &OPT, const vector<int> &P, vector<int> &sol, int j) {
    if (j <= 0) return;
    else if (schedules[j].weight + OPT[P[j]] > OPT[j]) {
        sol.push_back(j);
        return trace_back_intervals(schedules, OPT, P, sol, P[j]);
    }
    else return trace_back_intervals(schedules, OPT, P, sol, j - 1);
}

vector<int> interval_scheduling(vector<Schedule> schedules) {

    if (schedules.empty()) return vector<int>();

    sort(schedules.begin(), schedules.end(),
        [](const Schedule & a, const Schedule & b) {
        return a.end < b.end;
    });

    vector<int> subset_latest_valid = computeP(schedules);
    vector<int> OPT(schedules.size()+1, 0);
    for (int i = 1; i < OPT.size(); i++)
        OPT[i] = max(schedules[i - 1].weight + OPT[subset_latest_valid[i - 1]], OPT[i - 1]);

    vector<int> solution;
    trace_back_intervals(schedules, OPT, subset_latest_valid, solution, schedules.size()-1);
    return solution;

}

int main()
{
    vector<Schedule> schedules =
    { { 1,4 },{ 3,5 },{ 0,6 },{ 4,7 },
    { 3,8 },{ 5,9 },{ 6,10 },{ 8,11 } };

    vector<int> sol = interval_scheduling(schedules);
    for (int i : sol) cout << i << ' ';
    cout << endl;
}

Output: 

6 2