题解：P1803 凌乱的yyy / 线段覆盖

ChuMengLong · 2026-01-12 14:12:16 · 题解

题目传送门

解析

题目大意

简化题意：给出一些区间，选择一些区间进行覆盖，问最多可以同时覆盖多少区间，且满足没有任何一处是同时覆盖了两个区间？

考察知识

本题考查贪心算法。

思路

我们把每个区间输入头尾端点，然后进行排序：按照区间尾端点从小到大排序，注意：是尾端点而不能是头端点，因为如果是头端点的话可能会出现以下图的问题。 绿色区间明显相对红色区间更优，但是由于排头端点，所以会先选择红色区间，然后忽略绿色区间。

然后我们只需要枚举每一个区间，判断下一个区间的头端点是否大于当前区间的尾端点，如果满足则满足区间数量加一。

代码

#include<bits/stdc++.h>
using namespace std; 
struct node
{
    int starttime;
    int endtime;
}competition[100869100];

inline int cmp(node a,node b)
{
    if(a.endtime<b.endtime)
    {
        return 1;
    }
    return 0;
}

int main()
{
    int n,sum=1,statstarttime,j;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        cin>>competition[i].starttime>>competition[i].endtime;
    }
    sort(competition+1,competition+n+1,cmp);
    statstarttime=competition[1].endtime;
    while(j<=n)
    {
        j++;
        if(competition[j].starttime>=statstarttime)
        {
            sum++;
            statstarttime=competition[j].endtime;
        }
    }
    cout<<sum;
}

//meituideng