Merge Interval--LeetCode

- 日理万妓 2022-08-07 08:55 140阅读 0赞

# 题目： #

Given a collection of intervals, merge all overlapping intervals.

For example,  
Given `[1,3],[2,6],[8,10],[15,18]`,  
return `[1,6],[8,10],[15,18]`.

思路：

先按照每个区间的第一坐标来排序，然后再根据相邻两个区间判断合并，如果第一个区间的第二个不小于第二个区间的第一个坐标值，那么进行合并。

#include <iostream>
    #include <vector>
    #include <string> 
    #include <algorithm>
    using namespace std;
    
    /*
     Given a collection of intervals, merge all overlapping intervals.
    
    For example,
    Given [1,3],[2,6],[8,10],[15,18],
    return [1,6],[8,10],[15,18].
    
    */
    
    /*
    思路：合并区间 首先对区间进行排序，按照区间的第一个值进行排序 
    然后再处理重合的区间 
    */
    
    /*合并区间*/
     
    int compare(const pair<int,int>& first,const pair<int,int>& second)
    {
    	return first.first < second.first;
    } 
    
    
    void Merge_interval(vector<pair<int,int> >& interval)
    {
    	sort(interval.begin(),interval.end(),compare);
    	int i;
    	for(i=0;i<interval.size()-1;i++)
    	{
    		if(interval[i].second >= interval[i+1].first)
    		{
    			interval[i].second  = interval[i+1].second;
    			interval.erase(interval.begin()+i+1);
    			i--;
    		}
    	}
     
    }
     
     
    int main() 
    {
    	
    	vector<pair<int,int> > interval;
     	int i;
    	pair<int,int> pa(1,3);
    	pair<int,int> pa1(12,17);
    	pair<int,int> pa2(2,6);
    	pair<int,int> pa3(8,10);
    	pair<int,int> pa4(15,18);
    	 
    	
    	interval.push_back(pa);
    	interval.push_back(pa1);
    	interval.push_back(pa2);
    	interval.push_back(pa3);
    	interval.push_back(pa4);
    	
    	Merge_interval(interval);
    	
    	return 0;
    }

发表评论取消回复

表情：

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

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

相关阅读

相关 merge_sort

并排序是一种基于归并方法的排序。所谓归并是指将两个或两个以上的有序表合成一个新的有序表，包含所有元素。利用归并思想进行排序，可这样实现：首先将整个表看成是n个有序子表...

女爷i/ 2024年04月18日 22:50/ 0 赞/ 61 阅读

相关 Oracle写merge语录,Oracle MERGE语句

MERGE语句，它可以在一个SQL语句中对一张表或一个视图同时做更新或插入操作，避免了多个INSERT、UPDATE和DELETE语句。它可以从一个或多个数据源中选择数据对目标

忘是亡心i/ 2023年01月17日 15:55/ 0 赞/ 137 阅读

相关 git merge的三种操作merge, squash merge, 和rebase merge

原链接：[https://www.jianshu.com/p/ff1877c5864e][https_www.jianshu.com_p_ff1877c5864e]

女爷i/ 2022年12月30日 01:24/ 0 赞/ 202 阅读

相关 merge into

alter table GIC\_EXCEED\_STOCK\_SHARE\_APPLY add (auditmsg varchar2(100)); merge into

淩亂°似流年/ 2022年12月25日 14:58/ 0 赞/ 152 阅读

相关 merge-join

参考：1.https://www.cnblogs.com/xqzt/p/4469673.html 2.http://blog.itpub.net/20854791/view

清疚/ 2022年12月25日 11:52/ 0 赞/ 102 阅读

相关 merge

\--更新备注 merge into cust\_account\_im t using ( select nvl(aa.contact,cc.full\_name

怼烎@/ 2022年12月19日 03:40/ 0 赞/ 122 阅读

相关 mysql merge table

SELECT COUNT() FROM `comment` SHOW CREATE TABLE `comment` CREATE

我会带着你远行/ 2022年07月26日 04:08/ 0 赞/ 164 阅读

相关 merge用法

Merge关键字是一个神奇的DML关键字。它在SQL Server 2008被引入，它能将Insert,Update,Delete简单的并为一句。MSDN对于Merge的解释非

分手后的思念是犯贱/ 2022年06月07日 10:25/ 0 赞/ 379 阅读

相关 git merge

1. 合并分支时添加注释信息（只适用于non-fast-forward方式，该方式会生成新的commit。 fast-forward不会生成新的commit ） git m

红太狼/ 2022年05月15日 12:26/ 0 赞/ 200 阅读

相关 git merge简介

分享一下我老师大神的人工智能教程！零基础，通俗易懂！[http://blog.csdn.net/jiangjunshow][http_blog.csdn.net_jiangju

比眉伴天荒/ 2022年04月22日 14:10/ 0 赞/ 220 阅读