贪心算法区间不相交问题

xiaoxiao2021-02-28  10

#include #include using namespace std; const int maxn = 110; struct Inteval{ int left, right; }I[maxn]; bool cmp(Inteval a, Inteval b){ if (a.left != b.left) return a.left > b.left; else return a.right < b.right; } int main(){ int n; while (scanf("%d", &n), n != 0){ for (int i = 0; i < n; i++){ scanf("%d %d", &I[i].left, &I[i].right); } sort(I, I + n, cmp); int ans = 1, lastX = I[0].left; for (int i = 1; i < n; i++){ if (I[i].right <= lastX){ ans++; lastX = I[i].left; } } printf("%d", ans); } getchar(); return 0; }
转载请注明原文地址: https://www.6miu.com/read-450156.html

最新回复(0)