积分商城

最新搜索： stm32 jflash 人形机器人 CRC32校验工具 STC8H8K64S4U
您现在的位置是：首页 > 技术资料 > 链表与数组的综合应用：合并区间与插入区间
推荐星级：
  • 1
  • 2
  • 3
  • 4
  • 5

链表与数组的综合应用：合并区间与插入区间

更新时间：2026-10-17 10:43:20 大小：38K 上传用户：江岚查看TA发布的资源 标签：链表数组合并区间插入区间排序扫描 下载积分：2分 评价赚积分 （如何评价?） 打赏 收藏 评论(0) 举报

资料介绍

链表与数组的综合应用：合并区间与插入区间 一、合并区间问题 1.1 问题 给定多个区间，合并重叠的区间。 intervals = [[1,3],[2,6],[8,10],[15,18]]合并后 = [[1,6],[8,10],[15,18]] 1.2 排序+扫描 typedef struct { int start, end;} Interval;int compareInterval(const void *a, const void *b) { return ((Interval *)a)->start - ((Interval *)b)->start;}int mergeIntervals(Interval *intervals, int n, Interval *result) { if (n == 0) return 0; qsort(intervals, n, sizeof(Interval), compareInterval); int count = 0; result[count++] = intervals[0]; for (int i = 1; i < n; i++) { // 如果当前区间与前一个合并 if (intervals[i].start <= if="" .end=""> result[count-1].end) { result[count-1].end = intervals[i].end; } } else { result[count++] = intervals[i]; } } return count;} 核心：按开始时间排序，遍历时判断是否与已合并的最后一个区间重叠。 二、插入区间问题 2.1 问题 在一个已排序且不重叠的区间列表中插入一个新区间，保持不重叠。 intervals = [[1,3],[6,9]]insert [2,5]结果 = [[1,5],[6,9]] 2.2 三种情况处理 int insertInterval(Interval *intervals, int n, Interval newOne, Interval *result) { int count = 0; int i = 0; // 1. 新区间之前（end < new.start）的区间直接加入 while (i < n && intervals[i].end < newOne.start) { result[count++] = intervals[i++]; } // 2. 与新区间重叠的区间，合并 while (i < n && intervals[i].start <= newOne.end) { if (intervals[i].start < newOne.start) { newOne.start = intervals[i].start; } if (intervals[i].end > newOne.end) { newOne.end = intervals[i].end; } i++; } result[count++] = newOne; // 加入合并后的区间 // 3. 新区间之后的区间直接加入 while (i < n) { result[count++] = intervals[i++]; } return count;} 三种情况：新区间之前（不重叠）、与新区间重叠（合并）、新区间之后（不重叠）。 三、区间问题的其他应用 3.1 会议室安排 // 判断能否安排所有会议（区间不重叠）// 按结束时间排序，检查是否冲突 3.2 区间最值 // 在区间上求最大值（懒标记、线段树） 3.3 区间覆盖 // 用最少区间覆盖目标区间// 贪心：每次选择能覆盖当前起点的、结束最晚的区间 四、复杂度对比 五、总结 合并区间（排序+扫描判断重叠）和插入区间（三种情况处理）是区间问题的经典。理解"按开始排序"、"判断重叠"（start <= 已合并的end）、"合并取较大end"的核心逻辑，是解决区间类问题的基础。

部分文件列表

文件名 大小
链表与数组的综合应用：合并区间与插入区间.docx 38K

相关下载

全部评论(0)

暂无评论
评论赚积分>>

上传资源 上传优质资源有赏金

热门标签

更多>>

最新上传

  • 打赏
  • 30日榜单

热门下载

资料专题

推荐下载

本站上的所有资源均为源于网上收集或者由用户自行上传，仅供学习和研究使用，无任何商业目的，版权归原作如有侵权，请 来信指出，本站将立即改正。

ICP许可证号：京ICP证070360号     21IC电子网 2000- 版权所有

京ICP备11013301号

京公网安备 11010802024343号