โปรแกรมหาจำนวนหมุดน้อยสุดแขวนป้ายทั้งหมดใน C++

ให้ช่วง intervals = [start, end] แทนป้าย ต้องการหมุดน้อยสุดที่แผงทุกช่วง (หมุด 1 ตัวแขวนป้ายได้หลายแผ่นถ้าอยู่ในช่วง)

ตัวอย่าง: [[2,5],[5,6],[8,10],[10,13]] → 2 หมุด (ที่ 5 และ 10)

ขั้นตอนการแก้ปัญหา (Greedy)

1. เรียงช่วงตามจุดสิ้นสุด (end) น้อยไปมาก
2. last = -inf, ret = 0
3. วนแต่ละช่วง:
   • ถ้า last >= start: ข้าม (หมุดเดิมครอบคลุมแล้ว)
   • มิฉะนั้น: ret++, last = end (วางหมุดใหม่ที่จุดสิ้นสุดช่วงนี้)

การวางที่ end เป็น optimal เพราะครอบคลุมช่วงต่อไปมากที่สุด

ตัวอย่างโค้ด 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>>& v) {
        sort(v.begin(), v.end(), cmp);
        int ret = 0, last = -1e8;
        for (auto& it : v) {
            if (last >= it[0]) continue;
            ret++;
            last = it[1];
        }
        return ret;
    }
};

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

อินพุต

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

เอาต์พุต

2