区间合并（c++,java)

GeekLiHua

发布于 2025-01-21 21:48:07

3710

文章被收录于专栏：JavaJava

区间合并（c++,java)

给定一个长度为 n的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。

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

第二行包含 n个整数（均在 0∼105范围内），表示整数序列。

输出格式共一行，包含一个整数，表示最长的不包含重复的数的连续区间的长度。

数据范围 1≤n≤105 输入样例： 5 1 2 2 3 5 输出样例： 3

提交代码

c++

#include<bits/stdc++.h>
using namespace std;

typedef pair<int, int> PII;
vector<PII> segs;

void merge(vector<PII> &s)
{
    int st = -2e9, ed = -2e9;
    vector<PII> res;
    for (auto item:s)
    {
        if (ed < item.first)
        {
            res.push_back({st, ed});
            st = item.first, ed = item.second;
        }
        else ed = max(ed, item.second);
    }
    segs = res;
}

int main()
{
    int n;
    cin >> n;
    while(n --)
    {
        int l, r;
        cin >> l >> r;
        segs.push_back({l, r});
    }
    sort(segs.begin(), segs.end());
    merge(segs);
    cout << segs.size() << endl;
    return 0;
}

java

import java.util.*;

public class Main
{
    static int N = 100010;
    static int [] a;
    static ArrayList<int[]> list = new ArrayList<>();
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        for (int i = 0; i < n; ++ i)
        {
            a = new int [2];
            a[0] = in.nextInt();
            a[1] = in.nextInt();
            list.add(a);
        }
        list.sort(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });
        int k = 0;
        int r = Integer.MIN_VALUE;
        for (int a[]:list)
        {
            // 如果当前区间的左端点大于上一个区间的最右端
            // 那么这个区间就是个独立的区间 不需要合并
            if (a[0] > r) k ++;
            r = Math.max(r, a[1]);  // 更新右端点
        }
        System.out.println(k);
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-01-20，如有侵权请联系 cloudcommunity@tencent.com 删除

list