Sorting first, then greedy

A surprising number of contest problems become easy once the data is sorted in the right order: then a simple greedy rule (take the next item if it fits) is correct.

Sorting pairs

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

bool byEnd(const pair<int, int>& x, const pair<int, int>& y) {
    return x.second < y.second;
}

int main() {
    vector<pair<int, int>> v;
    v.push_back({3, 9});
    v.push_back({1, 5});
    v.push_back({3, 4});
    sort(v.begin(), v.end());
    for (auto& p : v) cout << "(" << p.first << "," << p.second << ") ";
    cout << "\n";
    sort(v.begin(), v.end(), byEnd);
    for (auto& p : v) cout << "(" << p.first << "," << p.second << ") ";
    cout << "\n";
    return 0;
}

Open in compiler

pair<int, int> holds two values, .first and .second. Pairs compare by first, then by second, so sort orders them naturally. Push a pair with push_back({a, b}).

To sort another way, pass a comparison function: sort(v.begin(), v.end(), byEnd) where byEnd(x, y) returns true when x must come before y.

A greedy choice after sorting

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

bool byEnd(const pair<int, int>& x, const pair<int, int>& y) {
    return x.second < y.second;
}

int main() {
    vector<pair<int, int>> meet = {{1, 4}, {3, 5}, {0, 6}, {5, 7}, {8, 9}, {5, 9}};
    sort(meet.begin(), meet.end(), byEnd);
    int count = 0, lastEnd = -1;
    for (auto& m : meet) {
        if (m.first >= lastEnd) {
            count++;
            lastEnd = m.second;
        }
    }
    cout << count << " meetings fit\n";
    return 0;
}

Open in compiler

The most meetings in one room: sort by end time, then take each meeting that starts after the last one taken ends. Finishing early always leaves the most room for the rest, which is why this greedy choice is optimal (the exchange argument from the Algorithms course).

Problem	Sort by	Greedy rule
most non-overlapping intervals	end	take if it starts after the last end
fewest platforms / rooms	start (with ends in a heap)	reuse the room that frees up first
minimise total waiting time	duration	shortest job first
assign biggest to biggest	value	pair them in order

Sorting pairs

A greedy choice after sorting

Quick check

Practice problems for this lesson

Sorting pairs

A greedy choice after sorting

Quick check

Practice problems for this lesson

Keep going