《剑指 Offer》专项突破版 - 面试题 74 : 合并区间(C++ 实现)

题目链接:LCR 074. 合并区间 - 力扣(LeetCode)

题目

输入一个区间的集合,请将重叠的区间合并。每个区间用两个数字表示,它们分别表示区间的起始位置和结束位置。例如,输入区间集合 [[1, 3], [4, 5], [8, 10], [2, 6], [9, 12], [15, 18]],合并重叠的区间之后得到 [[1, 6], [8, 12], [15, 18]]。

分析

首先需要考虑两个区间在什么情况下才能被合并。

  1. 如下图 (a) 所示,如果区间 1 的起始位置小于或等于区间 2 的起始位置,并且区间 1 的结束位置大于或等于区间 2 的起始位置,那么两个区间中间有重叠部分,它们能够合并,合并之后的区间的起始位置是区间 1 的起始位置,合并之后的区间的结束位置是两个区间的结束位置的较大者

  2. 反之,如下图 (b) 所示,如果区间 3 的起始位置小于区间 4 的起始位置,并且区间 3 的结束位置也小于区间 4 的起始位置,那么两个区间没有重叠部分,它们不能被合并。

如果先将所有区间按照起始位置排序,那么只需要比较前一个区间的结束位置和后一个区间的起始位置就能知道这两个相邻的区间是否重叠。如果它们重叠就将它们合并,然后判断合并的区间是否和下一个区间重叠。重复这个过程,直到所有重叠的区间都合并为止

例如,如果将区间集合 [[1, 3], [4, 5], [8, 10], [2, 6], [9, 12], [15, 18]] 按照起始位置排序就可以得到 [[1, 3], [2, 6], [4, 5], [8, 10], [9, 12], [15, 18]]。接下来扫描排序之后的区间集合。区间 [1, 3] 和 [2, 6] 重叠,可以合并,它们合并之后得到区间 [1, 6]。接下来的区间 [1, 6] 和 [4, 5] 重叠,可以合并,它们合并之后得到区间 [1, 6]。由于区间 [1, 6] 与下一个区间 [8, 10] 不重叠,因此将区间 [1, 6] 保存到合并之后的区间集合中,然后从区间 [8, 10] 开始与后面的区间合并。区间 [8, 10] 与它的下一个区间 [9, 12] 重叠,合并之后得到区间 [8, 12]。由于区间 [8, 12] 与下一个区间 [15, 18] 不重叠,因此将区间 [8, 12] 添加到合并之后的区间集合中,再从下一个区间 [15, 18] 开始合并之后的区间。最终合并之后的区间集合是 [[1, 6], [8, 12], [15, 18]]。

代码实现

struct LessCmpByStart {
    bool operator()(const vector<int>& lhs, const vector<int>& rhs)
    {
        return lhs[0] < rhs[0];
    }
};
​
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), LessCmpByStart());
​
        vector<vector<int>> mergedIntervals;
        int i = 0;
        while (i < intervals.size())
        {
            vector<int> tmp = { intervals[i][0], intervals[i][1] };
            int j = i + 1;
            while (j < intervals.size() && tmp[1] >= intervals[j][0])
            {
                if (intervals[j][1] > tmp[1])
                    tmp[1] = intervals[j][1];
                
                ++j;
            }
            mergedIntervals.push_back(tmp);
            i = j;
        }
        return mergedIntervals;
    }
};

该算法的时间复杂度是 O(nlogn)。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/436564.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【异常处理】BadSqlGrammarException低级SQL语法异常

报错 org.springframework.jdbc.BadSqlGrammarException: ### Error querying database. Cause: java.sql.SQLSyntaxErrorException: You have an error in your SQL syntax; check the manual that corresponds to your MySQL server version for the right syntax to use …

每日一练 | 华为认证真题练习Day194

1、下面是路由器Huawei的部分输出配置&#xff0c;关于该部分配置描迷正确的是: [huawei] bgp 100 [huawei-bgp]peer 12.12.12.2 ip-prefix P1 export [huawei]ip-prefix P1 index 5 deny 10.0.0.0 0 greater-equal 8 less-equal 32 [huawei]ip-prefix P1 index 5 deny 172…

做副业千万不要在抖音开个人店,个人店血泪史,千万别碰!

大家好&#xff0c;我是电商花花。 抖音小店个人店已经开放了很长时间了&#xff0c;个人店以不用营业执照&#xff0c;不用保证金&#xff0c;凭借身份证就可以在抖音上开抖音小店&#xff0c;就可以做电商&#xff0c;做老板。 目前抖音小店的流量可以说是非常大&#xff0…

【MetaGPT】多智能体协作——你画我猜(文字版)

多智能体协作 本篇将学习 MetaGPT中的 Environment 、 Team 组件。 1. Muti Agent 概念概述 多智能体系统 (Multi-Agent System, MAS) 是由一群具有一定自主性、协同性和学习能力的智能体组成的系统。智能体在环境中相互协作&#xff0c;以达到某种目标或完成特定任务。 2. 多…

哪里下载Mac上最全面的系统清理工具,CleanMyMac X4.15中文版永久版资源啊

哪里下载Mac上最全面的系统清理工具&#xff0c;CleanMyMac X4.15中文版永久版资源啊&#xff0c;CleanMyMac X4.15中文版是一款全面的Mac系统优化工具。它能够扫描、检测并清理不需要的文件和应用程序&#xff0c;优化内存使用和磁盘空间&#xff0c;提高Mac的性能表现。此外&…

运行json文件变成api服务器模拟,json-server

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 json-server数据运行 json-server数据运行 安装json-server // 命令 路径 端口 "server": "json-server ./server/data.json --port 8080",

LeetCode 2673. 使二叉树所有路径值相等的最小代价【贪心】1917

本文属于「征服LeetCode」系列文章之一&#xff0c;这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁&#xff0c;本系列将至少持续到刷完所有无锁题之日为止&#xff1b;由于LeetCode还在不断地创建新题&#xff0c;本系列的终止日期可能是永远。在这一系列刷题文章…

C语言指针总结(完结篇)

前言 这篇博客终于迎来了指针博客的大结局&#xff0c;本篇主要分析习题来回顾之前的指针总结的知识点&#xff0c;这篇博客的题有点绕&#xff0c;哈哈算是经典了 个人主页&#xff1a;小张同学zkf 若有问题 评论区见 感兴趣就关注一下吧 目录 1. sizeof和strlen的对比 1.1 …

Python算法100例-3.6 自守数

1.问题描述2.问题分析3.算法设计4.求给定数的位数5.分离给定数中的最后几位6.确定程序框架7.完整的程序 1&#xff0e;问题描述 自守数是指一个数的平方的尾数等于该数自身的自然数。例如&#xff0c; 5 2 25 &#xff0c; 2 5 2 625 &#xff0c; 7 6 2 5776 &#xff0c…

oss-fuzz-gen:一款基于LLM的模糊测试对象生成与评估框架

关于oss-fuzz-gen oss-fuzz-gen是一款基于LLM的模糊测试对象生成与评估框架&#xff0c;该工具可以帮助广大研究人员使用多种大语言模型&#xff08;LLM&#xff09;生成真实场景中的C/C项目以执行模糊测试。 该工具基于Google的OSS-Fuzz平台实现其功能&#xff0c;并对生成的…

参加美国大学生数学建模大赛,Matlab和Python该怎么选?

经常有小伙伴在数学建模竞赛会问到&#xff0c;MATLAB和Python到底哪个更好&#xff1f;这个问题一直困惑很多同学&#xff0c;今天数乐君来给大家从实用型来综合分析一下&#xff1a; 首先从两者各自的应用做个对比。 一、python的优势 Python相对于Matlab最大的优势&#…

光线追踪11 - Positionable Camera(可定位相机)

相机和介质一样&#xff0c;调试起来很麻烦&#xff0c;所以我总是逐步开发我的相机。首先&#xff0c;我们允许可调节的视野&#xff08;fov&#xff09;。这是渲染图像从一边到另一边的视觉角度。由于我们的图像不是正方形的&#xff0c;水平和垂直的视野是不同的。我总是使用…

初次实战SQL注入

目录 1.判断漏洞是否存在 2.判断注入类型&#xff08;数字型/字符型&#xff09; 3.猜列数 4.联合查询判断回显位 6.获取数据库表明 此实验为本人学习内容&#xff0c;从未攻击任何网站&#xff01;&#xff01;&#xff01;请伙伴们同样遵纪守法&#xff01;&#xff01;…

转录组总结

1. 软件安装 2.转录组分析步骤&#xff1a; ① 建立环境 #建立python2.7的环境&#xff0c;大部分的转录组信息都需要在Python2的环境下进行 conda create -n py2env python2.7 source activate py2env ② 获取fastqc报告 #单个报告 fastqc -t 15 /home/yinwen/biosoft/DN…

2024年数据库系统工程师全套资料

2024年5月数据库系统工程师全套视频、历年真题及解析、历年真题视频解析、教材、模拟题、重点笔记等资料 1、2023年5月、2022年5月、2021年5月数据库系统工程师全套基础精讲视频。2024年5月全套精讲视频持续更新中。 2、数据库系统工程师2004-2023年历年真题及解析文档&#x…

如何在Win系统部署Tomcat服务并实现远程访问内网站点

文章目录 前言1.本地Tomcat网页搭建1.1 Tomcat安装1.2 配置环境变量1.3 环境配置1.4 Tomcat运行测试1.5 Cpolar安装和注册 2.本地网页发布2.1.Cpolar云端设置2.2 Cpolar本地设置 3.公网访问测试4.结语 正文开始前给大家推荐个网站&#xff0c;前些天发现了一个巨牛的人工智能学…

读架构整洁之道的一些感悟

做产品开发时&#xff0c;我们经常跌落在一种无法打破的轮回中。 我们经常说&#xff0c;产品上线最重要&#xff0c;可以未来再重构代码&#xff0c; 但是结果大家都知道&#xff0c;产品上线以后重构工作就再没人提起了。首先&#xff0c;线上跑的好好的&#xff0c;动出问题…

动态规划(算法竞赛、蓝桥杯)--树形DP树的中心

1、B站视频链接&#xff1a;E34 树形DP 树的中心_哔哩哔哩_bilibili #include <bits/stdc.h> using namespace std; const int N20010; int n,a,b,c,ans2e9; struct edge{int v,w;}; vector<edge> e[N]; int d1[N],d2[N],path[N],up[N];//path记录d1 void dfs1(in…

【Vue】sessionStorage存取数据

一. 需求 1.1 模板 Vab Admin Pro 1.2 组件 ElementUI 1.3 阐述 列表页面搜索【关键词】点击【查询】后&#xff0c;点击【查看】按钮跳转到【详情页】&#xff0c;详情页【返回】【保留原搜索关键词】 原图 搜索查询【关键词】 详情 返回后【保留】【搜索查询关键词…

潜水耳机哪个牌子好?认准这几个游泳耳机品牌就对了!

在科技日益发达的今天&#xff0c;人们对于运动设备的需求也在不断提升。作为一项独特的水上运动&#xff0c;潜水爱好者们对耳机的要求也越来越高。一款优秀的潜水耳机不仅能够提供卓越的防水性能和舒适度&#xff0c;还必须具备出色的音质。那么&#xff0c;在众多品牌中&…