Acwing‘803. 区间合并

水深无声 2021-11-01 04:26 260阅读 0赞

（[https://www.acwing.com/problem/content/805/][https_www.acwing.com_problem_content_805]）

给定 nn 个区间 \[li,ri\]\[li,ri\]，要求合并所有有交集的区间。

注意如果在端点处相交，也算有交集。

输出合并完成后的区间个数。

例如：\[1,3\]和\[2,6\]可以合并为一个区间\[1,6\]。

#### 输入格式 ####

第一行包含整数n。

接下来n行，每行包含两个整数 l 和 r。

#### 输出格式 ####

共一行，包含一个整数，表示合并区间完成后的区间个数。

#### 数据范围 ####

1≤n≤1000001≤n≤100000,  
−109≤li≤ri≤109−109≤li≤ri≤109

#### 输入样例： ####

5
    1 2
    2 4
    5 6
    7 8
    7 9

#### 输出样例： ####

3
    
    
    思路：贪心。总的区间为n，每次合并一个区间，n--。注意处理边界问题：不能枚举到最后一个

#include <iostream>
    #include<vector>
    #include<algorithm>
    #include<cmath>
    using namespace std;
    typedef pair<int,int>pll;
    vector<pll> all;
    int main()
    {
        int n;
        cin >> n;
        for(int i=1;i<=n;i++)
        {
            int l,r;
            cin >> l >> r;
            all.push_back({l,r});
        }
        sort(all.begin(),all.end());
        int ans=n;
        for(int i=0;i<all.size()-1;i++)//不能枚举到最后一个
        {
            if(all[i].second>=all[i+1].first)
            {
                ans--;
                all[i+1].first=all[i].first;
                all[i+1].second=max(all[i+1].second,all[i].second);
            }
        }
        cout <<ans << endl;
        return 0;
    }

转载于:https://www.cnblogs.com/wjc2021/p/11168312.html

[https_www.acwing.com_problem_content_805]: https://www.acwing.com/problem/content/805/

发表评论取消回复

表情：

评论列表（有 0 条评论，260人围观）

还没有评论，来说两句吧...

相关阅读

相关 AcWing 422. 校门外的树（区间合并）

题目某校大门外长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在L的位置；数轴上的每个整数点，即0...

冷不防/ 2024年05月08日 06:10/ 0 赞/ 4 阅读

相关【算法|动态规划 | 区间dp No.1】AcWing 282. 石子合并

【算法|动态规划 | 区间dp No.1】AcWing 282. 石子合并

淩亂°似流年/ 2024年04月27日 07:02/ 0 赞/ 9 阅读

相关区间DP AcWing 282. 石子合并

区间DP AcWing 282. 石子合并原题链接 [AcWing 282. 石子合并][AcWing 282.] 算法标签动态规划区间DP 思路

拼搏现实的明天。/ 2023年09月28日 13:02/ 0 赞/ 65 阅读

相关区间合并 AcWing 803. 区间合并

区间合并 AcWing 803. 区间合并原题链接 [AcWing 803. 区间合并][AcWing 803.] 算法标签区间合并贪心思路

古城微笑少年丶/ 2023年09月28日 11:32/ 0 赞/ 60 阅读

相关区间问题 AcWing 907. 区间覆盖

区间问题 AcWing 907. 区间覆盖原题链接 [AcWing 907. 区间覆盖][AcWing 907.] 算法标签贪心思路 1.将所

小咪咪/ 2023年09月28日 11:01/ 0 赞/ 70 阅读

相关 56. 合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals\[i\] = \[starti, endi\] 。请你合并所有重叠的区间，并返回一个不重叠

快来打我*/ 2022年08月31日 07:19/ 0 赞/ 157 阅读

相关【leetcode】合并区间

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

超、凢脫俗/ 2022年03月08日 09:54/ 0 赞/ 220 阅读

相关合并区间

题目描述给出一个区间的集合，请合并所有重叠的区间。示例 1: 输入: [[1,3],[2,6],[8,10],[15,18]] 输出: [[1,6

傷城~/ 2022年01月22日 00:53/ 0 赞/ 224 阅读

相关 LeetCode：合并区间

给出一个区间的集合，请合并所有重叠的区间。 > 来源：力扣（LeetCode）链接：[https://leetcode-cn.com/problems/merge-inte

梦里梦外;/ 2021年11月16日 14:24/ 0 赞/ 279 阅读

相关 Acwing‘803. 区间合并

（[https://www.acwing.com/problem/content/805/][https_www.acwing.com_problem_content_805]

水深无声/ 2021年11月01日 04:26/ 0 赞/ 261 阅读