Chương trình tìm số ghim tối thiểu để treo tất cả băng rôn trong C++

Mô tả bài toán

Cho danh sách khoảng [start, end] đại diện cho băng rôn. Một ghim tại vị trí x treo được băng rôn nếu start ≤ x ≤ end. Tìm số ghim nhỏ nhất để treo tất cả băng rôn.

Ví dụ: intervals = [[2,5],[5,6],[8,10],[10,13]] → 2 ghim tại 5 và 10.

Giải thuật (Tham lam)

1. Sắp xếp các khoảng theo end tăng dần.
2. last = -INF, count = 0.
3. Duyệt từng khoảng: nếu last < start thì đặt ghim tại end (count++, last = end).

Ví dụ minh họa (C++)

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

class Solution {
public:
    static bool cmp(vector<int>& a, vector<int>& b) {
        return a.back() < b.back();
    }
    int solve(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), cmp);
        int ret = 0, last = -1e8;
        for (auto& it : intervals) {
            if (last >= it[0]) continue;
            ret++;
            last = it[1];
        }
        return ret;
    }
};

int solve(vector<vector<int>>& intervals) {
    return (new Solution())->solve(intervals);
}

int main() {
    vector<vector<int>> v = {{2,5},{5,6},{8,10},{10,13}};
    cout << solve(v);
    return 0;
}

Đầu vào

{{2,5},{5,6},{8,10},{10,13}}

Đầu ra

2