区间合并(c++,java)

简介: 区间合并(c++,java)

区间合并(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);
    }
}


相关文章
|
jenkins Shell 测试技术
|
安全 jenkins Java
Java、Python、C++支持jenkins和SonarQube(一)
Jenkins 是一个开源的 持续集成(CI)和持续交付(CD) 工具,用于自动化构建、测试和部署软件项目。它基于 Java 开发,支持跨平台运行,并拥有丰富的插件生态系统,可以灵活地扩展功能
708 5
|
jenkins Java Shell
Java、Python、C++支持jenkins和SonarQube(全集)
Jenkins 是一个开源的持续集成(CI)和持续交付(CD)工具,用于自动化构建、测试和部署软件项目。它基于 Java 开发,支持跨平台运行,并拥有丰富的插件生态系统,可以灵活地扩展功能
1052 1
|
jenkins Java 持续交付
Java、Python、C++支持Jenkins和SonarQube(三)
Python与Jenkins和SonarQube
642 1
|
jenkins Java 测试技术
|
算法 Java 数据库连接
Java 与 C++ 区别深入剖析及应用实例详解
本文深入剖析了Java和C++两种编程语言的区别,从编译与执行机制、面向对象特性、数据类型与变量、内存管理、异常处理等方面进行对比,并结合游戏开发、企业级应用开发、操作系统与嵌入式开发等实际场景分析其特点。Java以跨平台性强、自动内存管理著称,适合企业级应用;C++则因高性能和对硬件的直接访问能力,在游戏引擎和嵌入式系统中占据优势。开发者可根据项目需求选择合适语言,提升开发效率与软件质量。附面试资料链接:[点此获取](https://pan.quark.cn/s/4459235fee85)。
1232 0
|
Java Android开发 C++
Java和C++
Java和C++
485 15
|
IDE Java 程序员
C++ 程序员的 Java 指南
一个 C++ 程序员自己总结的 Java 学习中应该注意的点。
289 5
WK
|
安全 Java 编译器
C++和Java哪个更好用
C++和Java各具优势,选择取决于项目需求、开发者偏好及目标平台特性。C++性能出色,适合游戏、实时系统等;Java平台独立性强,适合跨平台、安全敏感应用。C++提供硬件访问和灵活编程范式,Java有自动内存管理和丰富库支持。两者各有千秋,需根据具体需求选择。
WK
713 1
|
缓存 并行计算 Java
C++矢量运算与java矢量运算
本文探讨了C++和Java中的矢量运算与标量运算的性能比较,解释了矢量运算的原理和为什么它比标量运算快,包括并行性、数据局部性、指令优化和数据重用等优势。文章还提供了C++和Java的矢量运算示例代码,并展示了运行结果,以证明矢量运算在处理大量数据时的性能优势。
574 0
C++矢量运算与java矢量运算