LeetCode Q56: Merge Intervals

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].

Nothing hard, but need to be careful when using vector::erase.

For example, when erase elements from i to j in A. 

When j>i, to remove [A[i], A[j]]:

erase(a.begin()+i, a.begin()+j+1)

because, erase(A.begin()+i, A.begin()+j), actually only remove [i, j) from A.

When j==i, to remove A[i]:

erase(A.begin()+i)

	/**
	* Definition for an interval.
	* struct Interval {
	* int start;
	* int end;
	* Interval() : start(0), end(0) {}
	* Interval(int s, int e) : start(s), end(e) {}
	* };
	*/
	class Solution {
	public:
	static bool myfunction(Interval& a, Interval& b){
	return a.start<b.start;
	}
	vector<Interval> merge(vector<Interval>& intervals) {
	sort(intervals.begin(), intervals.end(), myfunction);
	if(intervals.size()==0)
	return intervals;
	int startIdx=0;
	int end=intervals[0].end;
	for(int i=1; i<intervals.size(); ++i){
	Interval itv=intervals[i];
	if(itv.start<=end){
	end=max(itv.end, end);
	if(i==intervals.size()-1){
	if(i>startIdx+1)
	intervals.erase(intervals.begin()+startIdx+1, intervals.begin()+i+1);
	else
	intervals.erase(intervals.begin()+startIdx+1);
	intervals[startIdx].end=end;
	return intervals;
	}
	}else{
	//erase
	if(i-1>startIdx+1)
	intervals.erase(intervals.begin()+startIdx+1, intervals.begin()+i);
	if(i-1==startIdx+1)
	intervals.erase(intervals.begin()+startIdx+1);
	intervals[startIdx].end=end;
	i=startIdx+1;
	startIdx=i;
	end=intervals[i].end;
	}
	}
	return intervals;
	}
	};

view raw Q56MergeIntervals.cpp hosted with ❤ by GitHub

Round 2 solution:

	class Solution {
	public:
	static bool myfunction(Interval& a, Interval& b){
	return a.start<b.start;
	}
	vector<Interval> merge(vector<Interval>& intervals) {
	sort(intervals.begin(), intervals.end(), myfunction);
	vector<Interval> res;
	if(intervals.size()==0)
	return res;
	Interval newItv(intervals[0].start, intervals[0].end);
	for(int i=1; i<intervals.size(); i++){
	Interval itv = intervals[i];
	if(itv.start<=newItv.end)
	newItv.end=max(newItv.end, itv.end);
	else{
	res.push_back(newItv);
	newItv.start = itv.start;
	newItv.end = itv.end;
	}
	}
	res.push_back(newItv);
	return res;
	}
	};

view raw Q56-2.cpp hosted with ❤ by GitHub