区间合并算法的实现

算法一
贪心按左端点水过
思路：
就是以左端点进行排序，每次让下一个集合与该集合的右端点进行比较即可。

C++ 代码
#include
#include

using namespace std;

const int N = 1e5 + 10;

struct Range
{
int l,r;
bool operator< (const Range&W)const
{
return l < W.l;
}
}range[N]; //重载小于号，使其以左端点进行排序

int main()
{
int n;
cin >> n;
for(int i = 0;i < n;i ++)
{
int l,r;
scanf(“%d%d”,&l,&r);
range[i] = {l,r};
}

sort(range,range + n);

int res = 1;
int maxr = range[0].r;
for(int i = 1;i < n;i ++)
{
    if(range[i].l <= maxr) maxr = max(maxr,range[i].r);
    else
    {
        res ++;
        maxr = range[i].r;
    }
}

cout << res << endl;

return 0;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

}
算法二
贪心以右端点排序再次水过
思路：
思路与上一种差不多，不过右端点需要从右到左来合并区间

C++代码
#include
#include
#include

using namespace std;

const int N = 1e5 + 10;

struct Range
{
int l,r;
bool operator< (const Range&W)const
{
return r < W.r;
}
}range[N];

int main()
{
int n;
cin >> n;
for(int i = 0;i < n;i ++)
{
int l,r;
scanf(“%d%d”,&l,&r);
range[i] = {l,r};
}

sort(range,range + n);

int res = 1;
int maxl = range[n - 1].l;
for(int i = n - 2;i >= 0;i --)
{
    if(range[i].r >= maxl) maxl = min(maxl,range[i].l);
    else
    {
        res ++;
        maxl = range[i].l;
    }
}

cout << res << endl;

return 0;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

}
算法二
区间合并正常思路（y总解法）
思路：
非原创所以不配写思路

C++代码
#include

using namespace std;

typedef pair PII;
vector segs;

void merge(vector&segs)
{
vector res;
sort(segs.begin(),segs.end());
int l = -2e9,r = -2e9;
for(auto item:segs)
if(r < item.first)
{
if(l != -2e9) res.push_back({l,r});
l = item.first;
r = item.second;
}
else r = max(r,item.second);
if(l != -2e9) res.push_back({l,r});
segs = res;
}
int main()
{
int n;
cin >> n;

while(n--)
{
    int l,r;
    scanf("%d%d",&l,&r);
    segs.push_back({l,r});
}
merge(segs);
cout << segs.size() << endl;
return 0;
1
2
3
4
5
6
7
8
9

}

#include 
#include 
#include 
using namespace std ;
typedef pair<int,int> pii ;
vector<pii> nums,res ;
int main()
{
    int n ;
    scanf("%d",&n) ; 
    while(n--)
    {
        int l,r ; 
        scanf("%d%d",&l,&r) ;
        nums.push_back({l,r}) ;
    }
    sort(nums.begin(),nums.end()) ;                 //按左端点排序
    int st=nums[0].first,ed=nums[0].second ;        //ed代表区间结尾，st代表区间开头
    for(auto num:nums)                   
    {
        if(ed<num.first)                            //情况1：两个区间无法合并
        {
            res.push_back({st,ed}) ;                //区间1放进res数组
            st=num.first,ed=num.second ;            //维护区间2
        }
        //情况2：两个区间可以合并，且区间1不包含区间2，区间2不包含区间1
        else if(ed<num.second)  
            ed=num.second ;                         //区间合并
    }  
    //(实际上也有情况3：区间1包含区间2，此时不需要任何操作，可以省略)

    //注：排过序之后，不可能有区间2包含区间1

    if(st!=-2e9&&ed!=-2e9) res.push_back({st,ed});

    //考虑循环结束时的st,ed变量，此时的st,ed变量不需要继续维护，只需要放进res数组即可。因为这是最后的一个序列，所以不可能继续进行合并。

    /*
    for(auto r:res)
        printf("%d %d\n",r.first,r.second) ;
    puts("") ;
    */

    //(把上面的注释去掉，可以在调试时用)

    printf("%d",res.size()) ;           //输出答案
    return 0 ;
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50