[LeetCode] 56. Merge Intervals

轉自LeetCode

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

<Solution>

這題先看一些測資

[[1,3], [2,6], [8,10], [15,18]]

[[1,4], [0,5]]

[[1,4], [0,0]]

[[2,3], [4,5], [6,7], [8,9], [1,10]]

可以看到，start 的最小值和 end 的最大值，有可能在後面才會出現

這樣在處理上會比較複雜

因此，先針對 start value 來最排序，然後再針對 end value 來做 merge (參考資料)

code 如下

C++

	/**
	* 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 myCmp(const Interval &a, const Interval &b) {
	return a.start < b.start;
	}
	vector<Interval> merge(vector<Interval>& intervals) {
	vector<Interval> ans;
	if(intervals.empty()) {
	return ans;
	}
	//> sort according to start value
	sort(intervals.begin(), intervals.end(), myCmp);
	//> intervals[0].start is the min start
	ans.push_back(intervals[0]);
	for(int i = 1; i < intervals.size(); i++) {
	if(ans.back().end >= intervals[i].start) {
	ans.back().end = max(ans.back().end, intervals[i].end);
	}
	else {
	ans.push_back(intervals[i]);
	}
	}
	return ans;
	}
	};

view raw mergeIntervals_1.cpp hosted with ❤ by GitHub

Java

	/**
	* Definition for an interval.
	* public class Interval {
	* int start;
	* int end;
	* Interval() { start = 0; end = 0; }
	* Interval(int s, int e) { start = s; end = e; }
	* }
	*/
	class Solution {
	public List<Interval> merge(List<Interval> intervals) {
	Collections.sort(intervals, new IntervalCmp());
	LinkedList<Interval> ans = new LinkedList<>();
	for(Interval i : intervals) {
	if(ans.isEmpty() || ans.getLast().end < i.start) {
	ans.add(i);
	}
	else {
	ans.getLast().end = Math.max(ans.getLast().end, i.end);
	}
	}
	return ans;
	}
	private class IntervalCmp implements Comparator<Interval> {
	@Override
	public int compare(Interval a, Interval b) {
	return a.start < b.start ? -1 : a.start == b.start ? 0 : 1;
	}
	}
	}

view raw mergeIntervals.java hosted with ❤ by GitHub

Java 的另一種寫法

	/**
	* Definition for an interval.
	* public class Interval {
	* int start;
	* int end;
	* Interval() { start = 0; end = 0; }
	* Interval(int s, int e) { start = s; end = e; }
	* }
	*/
	class Solution {
	public List<Interval> merge(List<Interval> intervals) {
	Collections.sort(intervals, Comparator.comparingInt(o -> o.start));
	LinkedList<Interval> ans = new LinkedList<>();
	for(Interval i : intervals) {
	if(ans.isEmpty() || ans.getLast().end < i.start) {
	ans.add(i);
	}
	else {
	ans.getLast().end = Math.max(ans.getLast().end, i.end);
	}
	}
	return ans;
	}
	}

view raw mergeIntervals_2.java hosted with ❤ by GitHub

Kotlin

	class Solution {
	fun merge(intervals: Array<IntArray>): Array<IntArray> {
	val ans = arrayListOf<IntArray>()
	intervals.sortBy { it[0] }
	for(interval in intervals) {
	if(ans.isEmpty() || ans.last()[1] < interval[0]) {
	ans.add(interval)
	} else {
	ans.last()[1] = Math.max(ans.last()[1], interval[1])
	}
	}
	return ans.toTypedArray()
	}
	}

view raw merge_intervals.kt hosted with ❤ by GitHub