当前位置: 首页 > news >正文

力扣第56题 合并区间 c++ 贪心

题目

56. 合并区间

中等

相关标签

数组   排序

以数组 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] 可被视为重叠区间。

提示:

  • 1 <= intervals.length <= 104
  • intervals[i].length == 2
  • 0 <= starti <= endi <= 104

思路和解题方法

  • 思路是先对区间数组 intervals 按照区间的起始位置进行排序。然后,使用一个结果数组 ans 来存储合并后的区间。
  • 首先,将排序后的第一个区间加入结果数组 ans。
  • 然后,从第二个区间开始遍历,判断当前区间与结果数组中最后一个区间的关系:
  • 如果当前区间被包含在前一个区间中(即当前区间的结束位置小于等于前一个区间的结束位置),则无需合并,继续遍历下一个区间。
  • 如果当前区间与前一个区间有重叠部分(即当前区间的起始位置小于等于前一个区间的结束位置),则合并两个区间,更新前一个区间的结束位置为当前区间的结束位置。
  • 如果当前区间与前一个区间没有重叠部分,则直接将当前区间加入结果数组。
  • 最终,返回结果数组 ans 即为合并后的区间。

复杂度

        时间复杂度:

                O(nlogn)

时间复杂度分析:

  • 排序的时间复杂度为O(nlogn),其中n是区间的个数。
  • 遍历区间的时间复杂度为O(n),其中n是区间的个数。

因此,总的时间复杂度为O(nlogn)。

        空间复杂度

                O(n)

空间复杂度分析:

  • 结果数组ans的空间复杂度为O(n),其中n是区间的个数。

c++ 代码

class Solution {
public:static bool cmp(vector<int> &a, vector<int> &b) {return a[0] < b[0];} vector<vector<int>> merge(vector<vector<int>>& intervals) {vector<vector<int>> ans; // 存储合并后的区间结果if (intervals.size() == 0) return ans; // 如果输入为空,则直接返回空结果sort(intervals.begin(), intervals.end(), cmp); // 按区间的起始位置进行排序ans.push_back(intervals[0]); // 将第一个区间加入结果数组for (int i = 1; i < intervals.size(); i++) {if (ans.back()[1] >= intervals[i][1]) { // 当前区间被包含在前一个区间中,无需合并continue;} else if (ans.back()[1] >= intervals[i][0]) { // 当前区间与前一个区间有重叠部分,合并ans.back()[1] = intervals[i][1]; // 更新前一个区间的结束位置} else {ans.push_back(intervals[i]); // 当前区间与前一个区间无重叠部分,直接加入结果数组}}return ans;}
};

觉得有用的话可以点点赞,支持一下。

如果愿意的话关注一下。会对你有更多的帮助。

每天都会不定时更新哦  >人<  。

相关文章:

力扣第56题 合并区间 c++ 贪心

题目 56. 合并区间 中等 相关标签 数组 排序 以数组 intervals 表示若干个区间的集合&#xff0c;其中单个区间为 intervals[i] [starti, endi] 。请你合并所有重叠的区间&#xff0c;并返回 一个不重叠的区间数组&#xff0c;该数组需恰好覆盖输入中的所有区间 。 示例…...

php 日期

其中关于周的起止&#xff0c;使用date("N")&#xff0c;确保每周周一为起始&#xff0c;避免周日时出现作为新一周起始的情况 //获取上个月第一天 echo "上个月开始时间&#xff1a;".date(Y-m-01 00:00:00,strtotime(-1 month))."\r\n\r\n"; …...

食物链解读

[NOI2001] 食物链 题目描述 动物王国中有三类动物 A , B , C A,B,C A,B,C&#xff0c;这三类动物的食物链构成了有趣的环形。 A A A 吃 B B B&#xff0c; B B B 吃 C C C&#xff0c; C C C 吃 A A A。 现有 N N N 个动物&#xff0c;以 1 ∼ N 1 \sim N 1∼N 编号。…...

Day10配置文件日志多线程

配置文件 在企业开发过程中&#xff0c;我们习惯把一些需要灵活配置的数据放在一些文本文件中&#xff0c;而不是在Java代码写死 我们把这种存放程序配置信息的文件&#xff0c;统称为配置文件 properties 是一个Map集合&#xff08;键值对集合&#xff09;&#xff0c;但是我…...

leetcode:1154. 一年中的第几天(python3解法)

难度&#xff1a;简单 给你一个字符串 date &#xff0c;按 YYYY-MM-DD 格式表示一个 现行公元纪年法 日期。返回该日期是当年的第几天。 示例 1&#xff1a; 输入&#xff1a;date "2019-01-09" 输出&#xff1a;9 解释&#xff1a;给定日期是2019年的第九天。 示例…...

竞赛 深度学习图像修复算法 - opencv python 机器视觉

文章目录 0 前言2 什么是图像内容填充修复3 原理分析3.1 第一步&#xff1a;将图像理解为一个概率分布的样本3.2 补全图像 3.3 快速生成假图像3.4 生成对抗网络(Generative Adversarial Net, GAN) 的架构3.5 使用G(z)生成伪图像 4 在Tensorflow上构建DCGANs最后 0 前言 &#…...

flutter升级+生成drift文件

1. flutter升级 可以安装fvm进行flutter version manager FVM 安装笔记 - 掘金 (juejin.cn) 使用flutter upgrade, 但是没有效果&#xff0c; 可能需要到我的电脑中&#xff0c;更改高级系统设置&#xff1b;改变/增加环境变量&#xff1b;用来加上flutter官网获取信息的内…...

[AUTOSAR][诊断管理][ECU][$34] 下载请求

文章目录 一、简介二、服务请求报文定义肯定响应支持的NRC三、示例代码34_req_dowload.c一、简介 RequestDownload(0x34)—— 下载请求 这个服务主要是用来给ECU下载数据的,最常见的应用就是在bootloader中,程序下载工具会发起下载请求,以完成ECU程序的升级。 二、服务…...

C 标准库 - <errno.h>和<float.h>详解

目录 简介 常见库宏 简介 常见库宏 <errno.h> 简介 <errno.h>头文件定义了一个名为errno的全局变量&#xff0c;用于表示最近发生的错误代码。errno是一个整数变量&#xff0c;它的值通常是一个非零的错误代码&#xff0c;用于指示发生了什么类型的错误。也可以…...

对于如何学习的一点思考

目录 1、学习遇到的问题 2、问题分析 3、解决思路 1、学习遇到的问题 我们经常在学习一个知识时&#xff0c;经常会遇到知识点凌乱、读书效率低、缺乏长期记忆等问题&#xff0c;主要体现在&#xff1a; 知识点凌乱&#xff1a;花时间学习了很多技术点&#xff0c;但是由于…...

Ensemble Methods集成学习大比拼:性能、应用场景和可视化对比总结

集成学习(Ensemble Learning)是一种机器学习范式,其中多个模型(通常称为“弱学习器”)被训练以解决相同的问题,并且通过某种方式结合它们的预测以提高整体性能。这种方法的核心思想是,多个模型比单一模型更能准确地预测未知数据。在本文中,我们将探讨多种集成学习算法,…...

【2024秋招】2023-9-16 贝壳后端开发二面

1 自我介绍 2 秒杀系统 2.1 超卖怎么解决 3 redis 3.1 过期策略 3.2 过期算法 4 kafka 4.1 说一说你对kafka的了解 4.2 如何保证事务性消息 4.3 如何保证消息不丢失 4.4 消息队列的两种通信方式 点对点模式 如上图所示&#xff0c;点对点模式通常是基于拉取或者轮询…...

SpringCloud 微服务全栈体系(七)

第九章 Docker 一、什么是 Docker 微服务虽然具备各种各样的优势&#xff0c;但服务的拆分通用给部署带来了很大的麻烦。 分布式系统中&#xff0c;依赖的组件非常多&#xff0c;不同组件之间部署时往往会产生一些冲突。在数百上千台服务中重复部署&#xff0c;环境不一定一致…...

SAP ABAP 报表输出成 excel 统计图形 (RFC : GFW_PRES_SHOW_MULT)

SAP 预设了一个类型组 GFW &#xff0c;做简单的excel图形输出 话不多说&#xff0c;直接上代码&#xff1a; *&---------------------------------------------------------------------* *& Report ZCYCLE057 *&----------------------------------------------…...

微信小程序如何获取地理位置

在微信小程序中&#xff0c;可以通过以下步骤获取用户的地理位置&#xff1a; 在小程序的app.json文件中配置权限&#xff1a; json "permission": {"scope.userLocation": {"desc": "你的位置信息将用于获取附近的服务"} }这样配置后…...

计算机网络相关硬件介绍

计算机相关硬件 计算机由运算器、控制器、存储器、输入设备和输出设备等五个逻辑计算机硬件部件组成。 一、中央处理器&#xff08;CPU&#xff09;&#xff08;运算器、控制器&#xff09; &#xff08;1&#xff09;运算器 运算器是对数据进行加工处理的部件&#xff…...

Megatron-LM GPT 源码分析(三) Pipeline Parallel分析

引言 本文接着上一篇【Megatron-LM GPT 源码分析&#xff08;二&#xff09; Sequence Parallel分析】&#xff0c;基于开源代码 GitHub - NVIDIA/Megatron-LM: Ongoing research training transformer models at scale &#xff0c;通过GPT的模型运行示例&#xff0c;从三个维…...

Python---使用turtle模块+for循环绘制五角星---利用turtle(海龟)模块

首先了解涉及的新词汇&#xff0c;编程外国人发明的&#xff0c;所以大部分是和他们语言相关&#xff0c;了解对应意思&#xff0c;可以更好理解掌握。 import 英 /ˈɪmpɔːt/ n. 进口&#xff0c;进口商品&#xff1b;输入&#xff0c;引进&#xff1b;重要性&#xff1b;…...

Python的比较运算符查询表

据个人的编程开发经验&#xff0c;Python的比较运算符最常于条件判断&#xff0c;而条件判断是python编程中最常用的语法之一&#xff0c;与for或while的循环一样&#xff0c;功能十分强大&#xff01; 在机器学习当中&#xff0c;或深度学习当中&#xff0c;在运用算法对统计…...

C/C++面试常见问题——const关键字的作用和用法

首先我们需要一下const关键字的定义&#xff0c;const名叫常量限定符&#xff0c;当const修饰变量时&#xff0c;就是在告诉编译器该变量只可访问不可修改&#xff0c;而编译器对于被const修饰的变量有一个优化&#xff0c;编译器不会专门为其开辟空间&#xff0c;而是将变量名…...

uniapp 对接腾讯云IM群组成员管理(增删改查)

UniApp 实战&#xff1a;腾讯云IM群组成员管理&#xff08;增删改查&#xff09; 一、前言 在社交类App开发中&#xff0c;群组成员管理是核心功能之一。本文将基于UniApp框架&#xff0c;结合腾讯云IM SDK&#xff0c;详细讲解如何实现群组成员的增删改查全流程。 权限校验…...

深度学习在微纳光子学中的应用

深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向&#xff1a; 逆向设计 通过神经网络快速预测微纳结构的光学响应&#xff0c;替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...

第19节 Node.js Express 框架

Express 是一个为Node.js设计的web开发框架&#xff0c;它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用&#xff0c;和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...

python打卡day49

知识点回顾&#xff1a; 通道注意力模块复习空间注意力模块CBAM的定义 作业&#xff1a;尝试对今天的模型检查参数数目&#xff0c;并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...

<6>-MySQL表的增删查改

目录 一&#xff0c;create&#xff08;创建表&#xff09; 二&#xff0c;retrieve&#xff08;查询表&#xff09; 1&#xff0c;select列 2&#xff0c;where条件 三&#xff0c;update&#xff08;更新表&#xff09; 四&#xff0c;delete&#xff08;删除表&#xf…...

【大模型RAG】Docker 一键部署 Milvus 完整攻略

本文概要 Milvus 2.5 Stand-alone 版可通过 Docker 在几分钟内完成安装&#xff1b;只需暴露 19530&#xff08;gRPC&#xff09;与 9091&#xff08;HTTP/WebUI&#xff09;两个端口&#xff0c;即可让本地电脑通过 PyMilvus 或浏览器访问远程 Linux 服务器上的 Milvus。下面…...

在Ubuntu中设置开机自动运行(sudo)指令的指南

在Ubuntu系统中&#xff0c;有时需要在系统启动时自动执行某些命令&#xff0c;特别是需要 sudo权限的指令。为了实现这一功能&#xff0c;可以使用多种方法&#xff0c;包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法&#xff0c;并提供…...

vue3 定时器-定义全局方法 vue+ts

1.创建ts文件 路径&#xff1a;src/utils/timer.ts 完整代码&#xff1a; import { onUnmounted } from vuetype TimerCallback (...args: any[]) > voidexport function useGlobalTimer() {const timers: Map<number, NodeJS.Timeout> new Map()// 创建定时器con…...

【C语言练习】080. 使用C语言实现简单的数据库操作

080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...

Unit 1 深度强化学习简介

Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库&#xff0c;例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体&#xff0c;比如 SnowballFight、Huggy the Do…...