头像

风云学子

复旦大学


访客:2644

离线:1天前



题目描述

给定 n 个区间 $[l_i,r_i]$,要求合并所有有交集的区间。

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

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

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

输入格式
第一行包含整数n。

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

输出格式
共一行,包含一个整数,表示合并区间完成后的区间个数。

数据范围
$1≤n≤100000$,
$10^{-9}≤l_i≤r_i≤10{9}$

输入样例

5
1 2
2 4
5 6
7 8
7 9

输出样例

3

算法

首先构造一个pair数组,存储所有区间,然后使用sort()函数对其排序,时间复杂度为$O(nlogn)$,之后对数组进行遍历,时间复杂度为$O(n)$。
关键点在于对数组的遍历,使用 $sort()$ 排序后,可以保证数组中的pair按照左区间大小升序排列,在处理时,需要设置一个变量 $maxr$ 存储当前遍历到的最大右端点,只需判断当前pair的左端点是否小于已遍历pair的最大右端点。这句话是此题的关键,只要满足此条件,必然能够进行区间合并。若不满足,则区间总数++,开始搜索下一个区间,并更新 $maxr$ 的值为当前右端点。

时间复杂度 $O(nlogn)$

C++ 代码

#include <iostream>
#include <vector>
#include <algorithm>
#define l first
#define r second
using namespace std;
typedef pair<int, int> pii;
int n, x, y, res = 0, k = 0;
vector<pii> vec;

int main() {
    scanf("%d", &n);
    if(n == 1) {
      printf("0\n");
        return 0;      
    }
    for (int i = 0; i < n; i ++) {
        scanf("%d%d", &x, &y);
        vec.push_back({x, y});
    }
    sort(vec.begin(), vec.end());
    int maxr = vec[0].l;
    for(int i = 1; i < n; i ++) {
        pii cur = vec[i], last = vec[i-1];
        maxr = max(maxr, last.r);
        if(cur.l <= maxr) k ++;
        else    k = 1;
        if(k == 1) {
            maxr = cur.l;
            res ++;
        }
    }
    printf("%d\n", res);
    return 0;
}



活动打卡代码 AcWing 803. 区间合并

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#define l first
#define r second
using namespace std;
typedef pair<int, int> pii;
int n, x, y, res = 0, k = 0;
vector<pii> vec;

int main() {
    scanf("%d", &n);
    if(n == 1) {
      printf("0\n");
        return 0;      
    }
    for (int i = 0; i < n; i ++) {
        scanf("%d%d", &x, &y);
        vec.push_back({x, y});
    }
    sort(vec.begin(), vec.end());
    int maxr = vec[0].l;
    for(int i = 1; i < n; i ++) {
        pii cur = vec[i], last = vec[i-1];
        maxr = max(maxr, last.r);
        if(cur.l <= maxr) k ++;
        else    k = 1;
        if(k == 1) {
            maxr = cur.l;
            res ++;
        }
        //cout << "第" << i << "组测试:" << cur.l << ' ' << cur.r << " 结果" << res << endl;
    }
    printf("%d\n", res);
    return 0;
}


活动打卡代码 AcWing 802. 区间和

#include <iostream>
#include <algorithm>
#include <vector>
#define key first
#define val second
using namespace std;
typedef pair<int, int> PII;
const int N = 3e5+10;
int n, m;
vector<int> alls;       // 离散化前的所有数
vector<PII> ass, ask;   // ass赋值、 ask询问
int a[N], s[N];

int find(int k) {
    int l = 0, r = alls.size() - 1;
    while(l < r) {
        int mid = l+r >> 1;
        if(alls[mid] >= k) r = mid;
        else    l = mid + 1;
    }
    return r + 1;
}

int main() {
    int x, c, l, r, len;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++) {
        scanf("%d%d", &x, &c);
        ass.push_back({x,c});
        alls.push_back(x);
    }
    for (int i = 0; i < m; i ++) {
        scanf("%d%d", &l, &r);
        ask.push_back({l,r});
        alls.push_back(l);
        alls.push_back(r);
    }
    sort(alls.begin(), alls.end());
    alls.erase(unique(alls.begin(), alls.end()), alls.end());
    len = alls.size();
    for (auto item : ass) {
        a[find(item.key)] += item.val;
    }
    for (int i = 1; i <= len; i ++) {
        s[i] = s[i-1] + a[i];
    }
    for (auto item : ask) {
        l = find(item.key), r = find(item.val);
        printf("%d\n", s[r] - s[l-1]);
    }

    return 0;
}



#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5+5;
int a[N], b[N];
int n, m, x;

int main() {
    scanf("%d%d%d", &n, &m, &x);
    for (int i = 0; i < n; i ++) 
        scanf("%d", &a[i]);
    for (int i = 0; i < m; i ++)
        scanf("%d", &b[i]);
    for(int i = 0, j = m - 1; i < n; i ++) {   
         while(j >= 0 && a[i] + b[j] > x)   j --;
         if(a[i] + b[j] == x) {
             printf("%d %d\n", i, j);
             return 0;
         }
    }
    return 0;
}



#include <iostream>
using namespace std;

int lowbit(int n) {
    return n & -n;
}

int main() {
    int n, k;
    scanf("%d", &n);
    while(n --) {
        scanf("%d", &k);
        int cnt = 0;
        while(k != 0) {
            k -= lowbit(k);
            cnt ++;
        }
        printf("%d ", cnt);
    }
    return 0;
}



#include <iostream>
using namespace std;
const int N = 1e5+5;
int a[N], s[N];
int n, res = 0;
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i ++)
        scanf("%d", &a[i]);
    for (int i = 0, j = 0; i < n; i ++) {
        s[a[i]] ++;
        while(s[a[i]] > 1) {
            s[a[j]] --;
            j ++;
        }
        res = max(res, i - j + 1);
    }
    printf("%d\n", res);
    return 0;
}


活动打卡代码 AcWing 798. 差分矩阵

#include <iostream>
using namespace std;
const int N = 1010;
int n, m, q;
int a[N][N], b[N][N];
void insert(int x1, int y1, int x2, int y2, int c) {
    b[x1][y1] += c;
    b[x2+1][y1] -= c;
    b[x1][y2+1] -= c;
    b[x2+1][y2+1] += c;
}
int main() {
    scanf("%d%d%d", &n, &m, &q);
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++) {
            scanf("%d", &a[i][j]);
            insert(i, j, i, j, a[i][j]);
        }
    while(q --) {
        int x1, y1, x2, y2, c;
        scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c);
        insert(x1, y1, x2, y2, c);
    }
    for(int i = 1; i<= n; i ++)
        for(int j = 1; j <= m; j ++)
            b[i][j] =  b[i][j-1] + b[i-1][j] - b[i-1][j-1] + b[i][j];
    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= m; j ++)
            printf("%d ", b[i][j]);
        puts("");
    }
    return 0;
}



活动打卡代码 AcWing 797. 差分

#include <iostream>
using namespace std;
const int N = 1e5+10;
int a[N], b[N];
void insert(int l, int r, int c) {
    b[l] += c;
    b[r+1] -= c;
}

int main() {
    int n, m, l, r, c;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++) {
        scanf("%d", &a[i]);
        insert(i, i, a[i]);
    }
    while(m--) {
        scanf("%d%d%d", &l, &r, &c);
        insert(l, r, c);
    } 
    for(int i = 1; i <= n; i ++)
        b[i] += b[i-1];
    for(int i = 1; i <= n; i ++)
        printf("%d ", b[i]);
    return 0;
}


活动打卡代码 AcWing 796. 子矩阵的和

#include <iostream>
using namespace std;
const int N = 1e3+5;
int a[N][N], s[N][N];
int n, m, q;
int main() {
    scanf("%d%d%d", &n, &m, &q);
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++)
            scanf("%d", &a[i][j]);
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++)
            s[i][j] = s[i][j-1] + s[i-1][j] -s[i-1][j-1] + a[i][j];    
    while(q --) {
        int x1, y1, x2, y2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        printf("%d\n", s[x2][y2] - s[x2][y1-1] - s[x1-1][y2] + s[x1-1][y1-1]);
    }
    return 0;
}


活动打卡代码 AcWing 795. 前缀和

#include <iostream>
using namespace std;
const int N = 1e5+5;
int a[N], s[N];
int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++)
        scanf("%d", &a[i]);
    for(int i = 1; i <= n; i ++)
        s[i] = s[i-1] + a[i];
    while(m --) {
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%d\n", s[r] - s[l-1]);
    }
    return 0;
}