Merge Interval--LeetCode

- 日理万妓 2022-08-07 08:55 137阅读 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;
    }