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

区间合并笔记

文章目录

  • 什么是区间合并
  • 怎么做区间合并
  • AcWing 803. 区间合并
    • 思路解析
    • my - CODE
    • dalao の CODE



什么是区间合并

区间合并是指给定多个区间,让你将重合的区间合并为一个区间


怎么做区间合并

区间合并类问题大多三个办法:

  • 按左端点排序
  • 按右端点排序
  • 按左右端点双值排序

AcWing 803. 区间合并

题目链接:https://www.acwing.com/activity/content/problem/content/837/
区间和

思路解析

  • 我们按左端点大小将区间排序,排完序后从每个区间左端点开始遍历,我们会发现有三种情况
    • B区间在A
    • C区间有一部分与A重合
    • D区间在A
      三种情况
  • 我们的思路很明了了,通过两个指针:st(start),ed(end) 来标记我们正在维护的A数组的左右端点,往后遍历,处理三种情况
    • 如果遇到B:左端点不动,右端点也不动
    • 如果遇到C:左端点不动,右端点更新为C的右端点,也就是将A,C区间合并了
    • 如果遇到D:左右端点更新为D的左右端点,相当于现在改为维护D区间

my - CODE

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>using namespace std;typedef pair<int, int> pii;vector<pii> segs;			// 存储区间左右端点int main()
{int n, l, r;int ans = 0;cin >> n;while (n -- ){scanf("%d%d", &l, &r);segs.push_back({l, r});}sort(segs.begin(), segs.end());		// 以左端点优先排序int st = -1e9 - 1, ed = -1e9 - 1;	// 一开始的区间初始化为一个不可能的区间for(auto seg : segs){if(seg.first <= ed) ed = max(ed, seg.second);	// 有重合,右端点取最大else{			// 无重合,更新维护的区间ans++;st = seg.first;ed = seg.second;}}cout << ans << endl;
}

dalao の CODE

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;typedef pair<int, int> PII;void merge(vector<PII> &segs)
{vector<PII> res;sort(segs.begin(), segs.end());int st = -2e9, ed = -2e9;for (auto seg : segs)if (ed < seg.first){if (st != -2e9) res.push_back({st, ed});st = seg.first, ed = seg.second;}else ed = max(ed, seg.second);if (st != -2e9) res.push_back({st, ed});segs = res;
}int main()
{int n;scanf("%d", &n);vector<PII> segs;for (int i = 0; i < n; i ++ ){int l, r;scanf("%d%d", &l, &r);segs.push_back({l, r});}merge(segs);cout << segs.size() << endl;return 0;
}作者:yxc
链接:https://www.acwing.com/activity/content/code/content/40108/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
  • dalao将合并统计区间的过程抽出来单独写了个merge()函数,复用性和可读性更强
  • 而且将合并后的区间按秩存入了一个res空间,对于本题可能没有卵用,但是在其他区间合并问题中可能会用到合并后的区间
  • 不愧是dalao啊,orz %%%%%%

相关文章:

区间合并笔记

文章目录 什么是区间合并怎么做区间合并AcWing 803. 区间合并思路解析my - CODEdalao の CODE 什么是区间合并 区间合并是指给定多个区间&#xff0c;让你将重合的区间合并为一个区间 怎么做区间合并 区间合并类问题大多三个办法&#xff1a; 按左端点排序按右端点排序按左右…...

青少年CTF之PHP特性练习(1-5)

青少年CTF-PHP特性练习 文章目录 青少年CTF-PHP特性练习PHP特性01PHP特性02PHP特性03PHP特性04PHP特性05 PHP特性01 看给出的源码&#xff0c;两个变量的值加密后的MD5相同 <?php$s1 "%af%13%76%70%82%a0%a6%58%cb%3e%23%38%c4%c6%db%8b%60%2c%bb%90%68%a0%2d%e9%47…...

《opencv实用探索·七》一文看懂图像卷积运算

1、图像卷积使用场景 图像卷积是图像处理中的一种常用的算法&#xff0c;它是一种基本的滤波技术&#xff0c;通过卷积核&#xff08;也称为滤波器&#xff09;对图像进行操作&#xff0c;使用场景如下&#xff1a; 模糊&#xff08;Blur&#xff09;&#xff1a; 使用加权平…...

RPA机器人如何确保敏感数据的安全性

数据资源作为数字化时代的关键要素&#xff0c;其重要性一直受到高度重视&#xff0c;由此&#xff0c;数据安全也成为企业和个人必须面对的重要问题。随着RPA技术在各个行业的广泛应用&#xff0c;其系统安全性也成了每个企业关注的重中之重。经验丰富的RPA专家可以有效地采取…...

微信号被封了怎么办

13-7 常在河边走&#xff0c;哪有不湿鞋&#xff0c;做为经常用微信做电商客服的&#xff0c;或者经常在微信上和顾客谈钱的&#xff0c;总是会被微信后台重点关注&#xff0c;一不小心就有可能被封号。 如果遇到太倒霉的时候&#xff0c;永久封号了&#xff0c;这个时候微信…...

关于 ls -s 输出文件大小的单位问题的讨论

自己看书正好看到这里&#xff0c;正纳闷呢&#xff0c;上网查了下&#xff0c;发现不是我自己在为这个问题感到困惑。 有个大哥提出一个问题&#xff1a; 问题标题&#xff1a; ls -s的单位到底是什么&#xff1f; man ls -s, --size print the alloca…...

JSON.stringify方法详解 后端接受JSON数据格式

1、方法定义&#xff1a;JSON.stringify(value, replacer, space) 参数说明&#xff1a; value&#xff1a;js对象 replacer&#xff1a;替换对象&#xff0c;可以是一个方法、对象或数组&#xff0c;将value按照替换规则展示。 space&#xff1a;填充参数&#xff0c;可以是数…...

vue请求如何按顺序执行

我们有时候会碰到这种情况&#xff0c;需要连续发送两个请求&#xff0c;第二个请求需要用第一个请求的某个返回值作为参数来作为第二个请求的请求参数。 但是存在一个问题&#xff1a;两个请求都是异步的&#xff0c;他并不按照我们期望的先后顺序来执行。 这时候就需要控制请…...

【java】编译时bug 项目启动前bug合集

文章目录 1. jdk8中 Optional orElseThrow 编译时报错java: 未报告的异常错误X; 必须对其进行捕获或声明以便抛出2. 启动项目时提示 Error running Application: Command line is too long. Shorten command line for Application or also for Spring Boot default configurati…...

Pytorch——多卡GPU训练与单卡GPU训练相互切换

部分深度学习网络默认是多卡并行训练的&#xff0c;由于某些原因&#xff0c;有时需要指定在某单卡上训练&#xff0c;最近遇到一个&#xff0c;这里总结如下。 目录 一、多卡训练1.1 修改配置文件1.2 修改主训练文件1.3 显卡使用情况 二、单卡训练2.1 修改配置文件2.2 显卡使…...

Github项目-CNNResnet9-残差神经网络水果多分类项目

ResNet-论文全文完整翻译注解 - 知乎 你必须要知道CNN模型&#xff1a;ResNet - 知乎 #!/usr/bin/env python # coding: utf-8 #https://github.com/SehajS/cnn-resnet-fruit-classification # # Classifying Fruits from their Images # # This project aims at creating a…...

学习感悟一己之言

学习感悟一己之言 学习上克服困难实际上是克服心理上或认识上的障碍的过程。所谓的理解&#xff0c;就是化陌生为熟悉。看不懂&#xff0c;一方面是因为接触的材料太陌生&#xff0c;即远离你当前的背景知识&#xff1b;另一方面是材料或讲述者的描述刻画不准确或晦涩不当。有了…...

【设计模式-2.3】创建型——原型模式

说明&#xff1a;本文介绍设计模式中&#xff0c;创建型中的原型模式&#xff1b; 飞机大战 创建型设计模式关注于对象的创建&#xff0c;原型模式也不例外。如简单工厂和工厂模式中提到过的飞机大战这个例子&#xff0c;游戏中飞机、坦克对象会创建许许多多的实例&#xff0…...

八大插入算法(有注释)

直接插入排序 //直接插入排序 void InsertSortingDirectly(int* nums,int numsSize){int j0;for(int i1;i<numsSize-1;i){//定义一个中间变量保存当前要插入的值int tempnums[i];//在前面已排好序的序列中&#xff0c;找到合适的位置插入for(ji-1;j>0;j--){if(nums[j]&g…...

【2】基于多设计模式下的同步异步日志系统

6. 相关技术知识补充 6.1 不定参函数 在初学C语⾔的时候&#xff0c;我们都⽤过printf函数进⾏打印。其中printf函数就是⼀个不定参函数&#xff0c;在函数内部可以根据格式化字符串中格式化字符分别获取不同的参数进⾏数据的格式化。 ⽽这种不定参函数在实际的使⽤中也⾮常…...

npm管理发布包-创建与发布

创建与发布 我们可以将自己开发的工具包发布到 npm 服务上&#xff0c;方便自己和其他开发者使用&#xff0c;操作步骤如下 创建文件夹&#xff0c;并创建文件indexjs&#xff0c;在文件中声明函数&#xff0c;使用 module.exports 暴露npm初始化工具包&#xff0c;package.j…...

基于Spring,SpringMVC,MyBatis的校园二手交易网站

文章目录 项目介绍主要功能截图:部分代码展示设计总结项目获取方式🍅 作者主页:超级无敌暴龙战士塔塔开 🍅 简介:Java领域优质创作者🏆、 简历模板、学习资料、面试题库【关注我,都给你】 🍅文末获取源码联系🍅 项目介绍 基于Spring,SpringMVC,MyBatis的校园二…...

酒店 KPI绩效考核指标及应用

“路遥知马力&#xff0c;日久见人心”&#xff0c;目前国内各类型酒店风起云涌&#xff0c;大有在市场竞争中一比高下之势&#xff0c;各路精英受经济型酒店低投入高回报的市场利益驱动&#xff0c;都分分抢占市场&#xff0c;从而使国内经济型酒店的数量不断增加&#xff0c;…...

WordPress两种方法实现上传媒体图片文件自动重命名

我们发布文章时&#xff0c;会上传一些图片、音频之类的文件。但是WordPress没有自动 给新上传文件重命名的功能&#xff0c;逐个文件去重命名那就太麻烦了&#xff0c;那么我们改如何自动给上传的媒体文件图片重命名呢&#xff1f; 我在网站搜索了些上WordPress上传媒体文件自…...

TZOJ 1405 An easy problem

翻译有些出错&#xff0c;但大概是那个意思 答案&#xff1a; #include <stdio.h> #include <ctype.h> //引用库函数isupper的头文件int main() {int T 0, i 0;scanf("%d", &T); //要输入的行数while (T--) //循环T次{char c;int y 0…...

大数据学习栈记——Neo4j的安装与使用

本文介绍图数据库Neofj的安装与使用&#xff0c;操作系统&#xff1a;Ubuntu24.04&#xff0c;Neofj版本&#xff1a;2025.04.0。 Apt安装 Neofj可以进行官网安装&#xff1a;Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...

ES6从入门到精通:前言

ES6简介 ES6&#xff08;ECMAScript 2015&#xff09;是JavaScript语言的重大更新&#xff0c;引入了许多新特性&#xff0c;包括语法糖、新数据类型、模块化支持等&#xff0c;显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var&#xf…...

ArcGIS Pro制作水平横向图例+多级标注

今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作&#xff1a;ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等&#xff08;ArcGIS出图图例8大技巧&#xff09;&#xff0c;那这次我们看看ArcGIS Pro如何更加快捷的操作。…...

在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?

uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件&#xff0c;用于在原生应用中加载 HTML 页面&#xff1a; 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...

C++:多态机制详解

目录 一. 多态的概念 1.静态多态&#xff08;编译时多态&#xff09; 二.动态多态的定义及实现 1.多态的构成条件 2.虚函数 3.虚函数的重写/覆盖 4.虚函数重写的一些其他问题 1&#xff09;.协变 2&#xff09;.析构函数的重写 5.override 和 final关键字 1&#…...

【无标题】路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论

路径问题的革命性重构&#xff1a;基于二维拓扑收缩色动力学模型的零点隧穿理论 一、传统路径模型的根本缺陷 在经典正方形路径问题中&#xff08;图1&#xff09;&#xff1a; mermaid graph LR A((A)) --- B((B)) B --- C((C)) C --- D((D)) D --- A A -.- C[无直接路径] B -…...

Chrome 浏览器前端与客户端双向通信实战

Chrome 前端&#xff08;即页面 JS / Web UI&#xff09;与客户端&#xff08;C 后端&#xff09;的交互机制&#xff0c;是 Chromium 架构中非常核心的一环。下面我将按常见场景&#xff0c;从通道、流程、技术栈几个角度做一套完整的分析&#xff0c;特别适合你这种在分析和改…...

uniapp 小程序 学习(一)

利用Hbuilder 创建项目 运行到内置浏览器看效果 下载微信小程序 安装到Hbuilder 下载地址 &#xff1a;开发者工具默认安装 设置服务端口号 在Hbuilder中设置微信小程序 配置 找到运行设置&#xff0c;将微信开发者工具放入到Hbuilder中&#xff0c; 打开后出现 如下 bug 解…...

C++--string的模拟实现

一,引言 string的模拟实现是只对string对象中给的主要功能经行模拟实现&#xff0c;其目的是加强对string的底层了解&#xff0c;以便于在以后的学习或者工作中更加熟练的使用string。本文中的代码仅供参考并不唯一。 二,默认成员函数 string主要有三个成员变量&#xff0c;…...

Qt的学习(二)

1. 创建Hello Word 两种方式&#xff0c;实现helloworld&#xff1a; 1.通过图形化的方式&#xff0c;在界面上创建出一个控件&#xff0c;显示helloworld 2.通过纯代码的方式&#xff0c;通过编写代码&#xff0c;在界面上创建控件&#xff0c; 显示hello world&#xff1b; …...