Leetcode第56题(合并区间)

简介: 这篇文章介绍了LeetCode第56题“合并区间”的解题方法,通过排序和贪心策略合并重叠区间,并提供了C++的代码实现。

题目描述:

以数组 intervals 表示若干个区间的集合,其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间,并返回 一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间 。

示例 1:
输入:intervals = [[1,3],[2,6],[8,10],[15,18]]
输出:[[1,6],[8,10],[15,18]]
解释:区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2:
输入:intervals = [[1,4],[4,5]]
输出:[[1,5]]
解释:区间 [1,4] 和 [4,5] 可被视为重叠区间。

示例: intervals = [[1,3],[9,12],[2,6],[8,13],[15,18]]

遍历整个数组

遍历过程之中会出现三种情况:

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        //定义结果变量
        vector<vector<int>> ans;
        //排序
        sort(intervals.begin(),intervals.end());
        //定义一个区间的开始位置和结果位置
        int start = intervals[0][0],end = intervals[0][1];
        //遍历
        for(int i = 1; i< intervals.size();i++){
            //当前区间end < 下一个区间start (没有重叠部分)
            if(intervals[i][0] > end){
                ans.push_back({start,end});
                start = intervals[i][0];
                end = intervals[i][1];
            }else{          //有重叠部分
                end = max(end,intervals[i][1]);
            }
        }
        ans.push_back({start,end});

        return ans;
    }
};
相关文章
|
C++ 索引 容器
c++string容器-子串获取讲解
c++string容器-子串获取讲解
1412 0
|
XML Java 测试技术
『App自动化测试之Appium应用篇』| 元素定位工具Appium-Inspector从简介、安装、配置到使用的完整攻略
『App自动化测试之Appium应用篇』| 元素定位工具Appium-Inspector从简介、安装、配置到使用的完整攻略
3063 3
|
存储 缓存 编解码
Web端短视频编辑器的设计与实现 - 像做PPT一样做视频
对于视频的生产,一般的方案是交由专业机构去创作,但这将花费很多预算,如果我们能提供一个工具,基于知识的通用结构沉淀一些视频模版,让用户快速创作出视频知识内容岂不美哉?让想法再奔放些,如果我们能直接从知识库中抽取结构化的知识内容直接生成视频或是半成品视频,用户只需要稍作调整就能发布,这想想就很酷吧?是的,小蜜视频创作工具我就是想做这样一件事情。本篇分享来自阿里巴巴前端工程师李志成(敦固)在第十六届D2前端技术论坛的分享。
4262 0
Web端短视频编辑器的设计与实现 - 像做PPT一样做视频
|
8月前
|
SQL 搜索推荐 数据挖掘
检索的终局是决策:OLAP 如何重塑 Hologres 多模混合检索的价值边界
HSAP 2.0是Hologres提出的混合搜索与实时分析架构,首次将全文/向量检索与OLAP能力深度集成,实现“边查边算”。支持一条SQL完成语义匹配、结构化过滤与多维聚合,消除ETL延迟,保障强一致性,让检索系统从信息工具跃升为驱动商业决策的实时洞察引擎。
|
消息中间件 安全 Kafka
Kafka保证消息不丢失不重复
Kafka保证消息不丢失不重复
672 6
|
存储 算法
Leetcode第三题(无重复字符的最长子串)
这篇文章介绍了解决LeetCode第三题“无重复字符的最长子串”的算法,使用滑动窗口技术来找出给定字符串中最长的不含重复字符的子串,并提供了详细的代码实现和解释。
932 0
Leetcode第三题(无重复字符的最长子串)
|
Rust 安全 程序员
C++
C++诞生于对性能与控制的极致追求,融合C语言效率与面向对象思想,以“零开销抽象”和信任程序员为核心哲学。历经四十年演进,从系统底层到前沿科技,其力量源于复杂性,挑战亦然。现代C++在安全与效率间持续进化,仍是驾驭硬件、突破极限的不二之选。
|
存储 人工智能 自然语言处理
DeepSeek R1+Ollama+Cherry Studio实现本地知识库的搭建
本文介绍了如何使用Ollama和CherryStudio搭建本地知识库,涵盖核心组件介绍、硬件与软件准备、模型部署流程及知识库构建方法。通过配置DeepSeek R1模型、嵌入模型和Cherry Studio平台,实现本地化自然语言处理与知识检索功能。
4129 0
|
Linux Docker 容器
Linux的namespace和cgroups简介
本文介绍了Linux的Namespace技术和cgroups,解释了它们如何帮助实现容器的隔离和资源限制。
805 7
Linux的namespace和cgroups简介
|
机器学习/深度学习 人工智能 监控
一文读懂deepSpeed:深度学习训练的并行化
DeepSpeed 是由微软开发的开源深度学习优化库,旨在提高大规模模型训练的效率和可扩展性。通过创新的并行化策略、内存优化技术(如 ZeRO)及混合精度训练,DeepSpeed 显著提升了训练速度并降低了资源需求。它支持多种并行方法,包括数据并行、模型并行和流水线并行,同时与 PyTorch 等主流框架无缝集成,提供了易用的 API 和丰富的文档支持。DeepSpeed 不仅大幅减少了内存占用,还通过自动混合精度训练提高了计算效率,降低了能耗。其开源特性促进了 AI 行业的整体进步,使得更多研究者和开发者能够利用先进优化技术,推动了 AI 在各个领域的广泛应用。
10932 21