首页 > itarticle > [luogu p1803] 线段覆盖

[luogu p1803] 线段覆盖

admin 11月 13, 2020 0

Luogu P1803

题目大意 ：给定 $ n $ 条线段，现要选取其中 $ k $ 条线段使得这 $ k $ 条线段两两没有重合部分，问最大的 $ k $ 为多少?
主要思路 ：贪心。首先用结构体储存这些边的起点和终点，对这 $ n $ 条线段按照结束时间升序排序，如果 now_time <= edge[i].start ,就更新 now_time = edge[i].end .

代码


#include <cstdio>
#include <algorithm>

using namespace std;

struct  {int start, end;} match[1000010];

bool cmp(Match x,Match y) {return x.end < y.end;}

int now_time = 0,ans = 0;

int main() {
	int n;
	scanf("%d",&n);
	for(int i = 1;i <= n;i++) {
		scanf("%d%d",&match[i].start,&match[i].end);
    }
    sort(match + 1,match + n + 1,cmp);
    for(int i = 1;i <= n;i++) {
    	if(now_time <= match[i].start) {
    		ans ++;
    		now_tome = match[i].end;
		}
	}
	printf("%d",ans);
	return 0;
}