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

leetcode0056. 合并区间 - medium

1 题目:合并区间

官方难度 - 中等

以数组 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 < = i n t e r v a l s . l e n g t h < = 1 0 4 1 <= intervals.length <= 10^4 1<=intervals.length<=104
i n t e r v a l s [ i ] . l e n g t h = = 2 intervals[i].length == 2 intervals[i].length==2
0 < = s t a r t i < = e n d i < = 1 0 4 0 <= start_i <= end_i <= 10^4 0<=starti<=endi<=104

2 solution

最直接的做法,先按照 start 排序,然后进行合并,步骤如下:

1 先按照 start 递增排序
2 初始化 s = start[0], e = end[0]
3 对于之后的每一个intervals[i],如果 start[i] 在区间[s, e] 内,则说明可以合并,否则是一个新的区间。

代码

class Solution {
public:
   vector<vector<int>> merge(vector<vector<int>> &intervals) {
    vector<vector<int>> result;
    sort(intervals.begin(), intervals.end());

    int start = intervals[0][0], end = intervals[0][1];
    int i = 1;
    while (i < intervals.size()) {
        if (intervals[i][0] > end) {
            result.push_back({start, end});
            start = intervals[i][0];
        }
        end = max(end, intervals[i][1]);
        i++;
    }
    result.push_back({start, end});
    return result;
}
};

结果

在这里插入图片描述


http://www.kler.cn/a/584570.html

相关文章:

  • SQL Server性能优化实战:从瓶颈定位到高效调优
  • R+VIC模型融合实践技术应用及未来气候变化模型预测
  • Oracle获取SQL执行日志
  • 深度学习基础-onnxruntime推理模型
  • 如何通过自动化测试提升DevOps效率?
  • Axure PR 9 中继器 04 条件查询
  • MySQL与Redis的缓存一致性问题
  • 【linux】文件与目录命令 - stat
  • 使用Python在Word中生成多种不同类型的图表
  • JVM类加载机制和双亲委派
  • 江科大51单片机笔记【16】AD/DA转换(下)
  • Arbitrum之智能合约
  • Java 虚拟机优化指南:CMS垃圾回收器参数调优与性能监控工具详解
  • 【数据结构】初识集合框架及背后的数据结构(简单了解)
  • uniapp移动端图片比较器组件,仿英伟达官网rtx光追图片比较器功能
  • Java --- 根据身份证号计算年龄
  • 《基于大数据的营养果蔬推荐系统的设计与实现》开题报告
  • makefile详解
  • Discuz建站教程之论坛头部logo跳转链接怎么修改?
  • HCIA复习实验拓扑详细版