Interval scheduling (Greedy Sub-pattern)

// Most non-overlapping intervals: take the one that ends first, again and again.
// Touching ([1,3] then [3,5]) allowed here; use > instead of >= if the problem forbids it.
int maxNonOverlapping(vector<pair<int,int>> iv) {          // {start, end}
    sort(iv.begin(), iv.end(), [](auto& a, auto& b) { return a.second < b.second; });
    int count = 0;
    long long lastEnd = LLONG_MIN;
    for (auto& [s, e] : iv)
        if (s >= lastEnd) { count++; lastEnd = e; }         // fits after the last one taken
    return count;
}

// Partition into most parts: a part must reach the last occurrence of each of its letters.
vector<int> partitionByLast(const string& s) {
    int last[26] = {};
    for (int i = 0; i < (int)s.size(); i++) last[s[i] - 'a'] = i;
    vector<int> sizes;
    int start = 0, end = 0;
    for (int i = 0; i < (int)s.size(); i++) {
        end = max(end, last[s[i] - 'a']);
        if (i == end) { sizes.push_back(end - start + 1); start = i + 1; }   // part closed
    }
    return sizes;
}