LeetCode [56] Merge Intervals

 56. Merge Intervals

Medium

Given a collection of intervals, merge all overlapping intervals.

Example 1:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

Example 2:

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

 

Constraints:

• intervals[i][0] <= intervals[i][1]

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

//C++: 588 ms /** * Definition for an interval. * struct Interval { * int start; * int end; * Interval() : start(0), end(0) {} * Interval(int s, int e) : start(s), end(e) {} * }; */ bool compare(const Interval &a, const Interval &b){ return a.start<b.start; } class Solution { public: vector<Interval> merge(vector<Interval>& intervals) { sort(intervals.begin(), intervals.end(), compare); vector<Interval> res; int n = intervals.size(); int i = 0; while(i<n){ int j = i+1; while(j<n && intervals[i].end>=intervals[j].start){ intervals[i].end = max(intervals[i].end, intervals[j].end); j++; } res.push_back(intervals[i]); i = j; } return res; } };

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

class Solution { public int[][] merge(int[][] intervals) { Arrays.sort(intervals, (a,b)->a[0]-b[0]); int n = intervals.length; int i = 0; List<int[]> list = new ArrayList<>(); while(i<n){ int start = intervals[i][0], end = intervals[i][1]; int j=i+1; while(j<n && intervals[j][0]<=end){ end = Math.max(end, intervals[j][1]); j++; } list.add(new int[]{start, end}); i = j; } return list.toArray(new int[0][]); } }