LeetCode56——Merge Intervals

淡淡的烟草味﹌ 2022-08-09 12:56 105阅读 0赞

LeetCode56——Merge Intervals

题意：

简单理解就是对区间序列做高中数学里面的并运算。

现在假设几种情况：

\[1,2\]∪\[3,4\]的并集表示就是\{ \[1,2\]∪\[3,4\] \} 即，无交集集合的并运算

\[1,3\]∪\[2,4\]的并集表示就是\{ \[1,4\] \} 即，有交集集合的并运算

\[1,4\]∪\[2,3\]的并集表示就是\{ \[1,4\] \} 即，有包含关系的集合的并运算

综合上述三种情况：

1.第二种和第三种是可以合并的。根据这两种情况，编写可以合并的代码，对整个序列遍历合并。

2.在此之前需要对序列中的元素按照start的值从小到大排序。

结合上述1.2代码如下：

bool cmp(const Interval &a, const Interval &b)
    {
    	return a.start < b.start;
    }
    class Solution {
    private:
    	bool canMerge(Interval &a, Interval &b)//可以合并的情况
    	{
    		if (a.end >= b.start&&a.end<=b.end)
    		{
    			a.end = b.end;
    			return true;
    		}
    		else if (a.end > b.end)
    		{
    			return true;
    		}
    		return false;
    	}
    public:
    	vector<Interval> merge(vector<Interval>& intervals) {
    		int i = 0;
    		int j;
    		vector<Interval>result;
    		sort(intervals.begin(), intervals.end(),cmp);
    		while (i < intervals.size())
    		{
    			j = i+1;
    			while (j<intervals.size()&&canMerge(intervals[i], intervals[j]))
    				j++;
    			result.push_back(intervals[i]);
    			i = j;//一次合并完成，更新判断起点
    		}
    		return result;
    	}
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，105人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode56——Merge Intervals

LeetCode56——Merge Intervals 题意：简单理解就是对区间序列做高中数学里面的并运算。现在假设几种情况： \[1,2\]∪\[3,4\]的并集

淡淡的烟草味﹌/ 2022年08月09日 12:56/ 0 赞/ 106 阅读

相关【LeetCode】56. Merge Intervals

56. Merge Intervals Given a collection of intervals, merge all overlapping intervals

Dear 丶/ 2022年07月26日 05:19/ 0 赞/ 118 阅读

相关 leetcode 56. Merge Intervals

Given a collection of intervals, merge all overlapping intervals. For example, Given

迷南。/ 2022年07月25日 19:27/ 0 赞/ 130 阅读

相关 leetcode 56. Merge Intervals 区间合并

Given a collection of intervals, merge all overlapping intervals. For example, Given

骑猪看日落/ 2022年06月09日 10:54/ 0 赞/ 111 阅读

相关 [Leetcode]-56 Merge Intervals

![70][] 在解决这个问题的时候，我的思路是： Interval的形式为（start,end） 1）按照Interval的第一个数值start进行排序，得到排序后数组

小鱼儿/ 2022年05月24日 06:37/ 0 赞/ 112 阅读

相关 LeetCode 56.Merge Intervals (合并区间)

题目描述: 给出一个区间的集合，请合并所有重叠的区间。示例 1: 输入: [[1,3],[2,6],[8,10],[15,18]] 输出: [[1,6]

今天药忘吃喽~/ 2022年05月10日 03:50/ 0 赞/ 119 阅读

相关 LeetCode：56. Merge Intervals（合并区间）

> 文章最前：我是Octopus，这个名字来源于我的中文名--章鱼；我热爱编程、热爱算法、热爱开源。所有源码在我的个人[github][] ；这博客是记录我学习的点点滴滴，如

怼烎@/ 2022年04月05日 13:44/ 0 赞/ 159 阅读

相关【Leetcode】56. Merge Intervals（模拟）

Given a collection of intervals, merge all overlapping intervals. Example 1: Input

「爱情、让人受尽委屈。」/ 2022年02月28日 00:50/ 0 赞/ 121 阅读

相关 56. Merge Intervals

class Solution { public List<Interval> merge(List<Interval> intervals) {

待我称王封你为后i/ 2021年12月22日 06:49/ 0 赞/ 164 阅读

相关 LeetCode : 56. Merge Intervals 合并区间

试题 Given a collection of intervals, merge all overlapping intervals. Example 1: Inpu

矫情吗；*/ 2021年06月24日 16:11/ 0 赞/ 358 阅读