侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 675 篇文章
  • 累计创建 128 个标签
  • 累计收到 26 条评论

目 录CONTENT

文章目录

【排序, 双指针】区间合并

GabrielxD
2022-10-27 / 0 评论 / 0 点赞 / 332 阅读 / 753 字
温馨提示:
本文最后更新于 2022-11-11,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

803. 区间合并


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

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

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

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

输入格式

第一行包含整数 nn

接下来 nn 行,每行包含两个整数 llrr

输出格式

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

数据范围

1n1000001 \le n \le 100000,
109liri109-10^9 \le l_i \le r_i \le 10^9

输入样例:

5
1 2
2 4
5 6
7 8
7 9

输出样例:

3

解题

方法一:排序 双指针

思路

首先把所有区间按左端点升序排序,使用双指针(sted)维护一个当前区间,初始化为无穷小(NEG_INF),然后正向遍历区间数组,此时区间 [st,ed][st, ed] 与区间 [seg[0],seg[1]][seg[0], seg[1]] 之间的关系分为两种情况:

  1. 区间相交,edseg[0]ed \ge seg[0],此时区间可以合并,区间的右端点变为 max(ed,seg[1])max(ed, seg[1])
  2. 区间不相交,ed<seg[0]ed < seg[0],此时区间不能合并,把当前区间加入结果数组(res)并把当前遍历到的区间置为当前区间。

遍历完成后别忘了把最后一个区间加入结果数组(如果区间合法的话)。

代码

import java.util.*;
import java.io.*;

public class Main {
    static final int NEG_INF = (int) -2e9;
    static List<int[]> segs = new ArrayList<>();
    
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        while (n-- > 0) {
            in.nextToken();
            int l = (int) in.nval;
            in.nextToken();
            int r = (int) in.nval;
            segs.add(new int[]{l, r});
        }
        System.out.println(merge(segs).size());
    }
    
    static List<int[]> merge(List<int[]> segs) {
        segs.sort((a, b) -> a[0] - b[0]);
        List<int[]> res = new ArrayList<>();
        int st = NEG_INF, ed = NEG_INF;
        for (int[] seg : segs) {
            if (ed < seg[0]) {
                if (st != NEG_INF) res.add(new int[]{st, ed});
                st = seg[0];
                ed = seg[1];
            } else ed = Math.max(ed, seg[1]);
        }
        if (st != NEG_INF) res.add(new int[]{st, ed});
        return res;
    }
}
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

int n;
vector<PII> intervals;

int main () {
    scanf("%d", &n);
    while (n-- > 0) {
        int l, r;
        scanf("%d%d", &l, &r);
        intervals.push_back({l, r});
    }
    sort(intervals.begin(), intervals.end(), [] (auto& a, auto& b) {
        return a.first < b.first;
    });
    int cnt = 0;
    int st = -2e9, ed = -2e9;
    for (auto& interval : intervals) {
        if (ed < interval.first) {
            if (st != -2e9) ++cnt;
            st = interval.first, ed = interval.second;
        } else ed = max(ed, interval.second);
    }
    if (st != -2e9) ++cnt;
    printf("%d\n", cnt);
    
    return 0;
}
0

评论区