BiruLyu
7/28/2017 - 6:44 PM

## 56. Merge Intervals(#).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; }
* }
*/
public class Solution {
public List<Interval> merge(List<Interval> intervals) {
List<Interval> rst = new ArrayList<Interval>();
if(intervals == null) {
return rst;
}

int n = intervals.size();
int[] start = new int[n];
int[] end = new int[n];
for(int i = 0; i < n; ++i) {
start[i] = intervals.get(i).start;
end[i] = intervals.get(i).end;
}

Arrays.sort(start);
Arrays.sort(end);

for(int last = 0, cur = 0; cur < n; ++cur) {
if(cur == n-1 || start[cur+1] > end[cur]) {
last = cur+1;
}
}

return rst;
}
}``````
``````/**
* 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; }
* }
*/
public class Solution {
public List<Interval> merge(List<Interval> intervals) {
List<Interval> rst = new ArrayList<Interval>();
if(intervals == null) {
return rst;
}

int n = intervals.size();
int[] start = new int[n];
int[] end = new int[n];
for(int i = 0; i < n; ++i) {
start[i] = intervals.get(i).start;
end[i] = intervals.get(i).end;
}

Arrays.sort(start);
Arrays.sort(end);

for(int last = 0, cur = 0; cur < n; ++cur) {
if(cur == n-1 || start[cur+1] > end[cur]) {
last = cur+1;
}
}

return rst;
}
}``````
``````/**
* 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; }
* }
*/
public class Solution {
public List<Interval> merge(List<Interval> intervals) {
int n = intervals.size();
int[] starts = new int[n];
int[] ends = new int[n];
for (int i = 0; i < n; i++) {
starts[i] = intervals.get(i).start;
ends[i] = intervals.get(i).end;
}
Arrays.sort(starts);
Arrays.sort(ends);
// loop through
List<Interval> res = new ArrayList<Interval>();
for (int i = 0, j = 0; i < n; i++) { // j is start of interval.
if (i == n - 1 || starts[i + 1] > ends[i]) {
j = i + 1;
}
}
return res;
}
}``````
``````/**
* 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; }
* }
*/
public class Solution {
public List<Interval> merge(List<Interval> intervals) {
if (intervals == null || intervals.size() == 0) {
return intervals;
}
Collections.sort(intervals, new Comparator<Interval>() {
public int compare(Interval i1, Interval i2) {
if (i1.start != i2.start) {
return i1.start - i2.start;
} else {
return i1.end - i2.end;
}
}
});
List<Interval> result = new ArrayList<Interval>();
for (int i = 1; i < intervals.size(); i++) {
Interval last = result.get(result.size() - 1);
Interval current = intervals.get(i);
if (last.end < current.start) {
} else {
last.end = Math.max(last.end, current.end);
}
}
return result;
}
}``````
``````/**
* 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; }
* }
*/
public class Solution {
public List<Interval> merge(List<Interval> intervals) {
if (intervals == null || intervals.size() < 2) return intervals;
int len = intervals.size();
Collections.sort(intervals, new Comparator<Interval>(){
public int compare (Interval a, Interval b) {
if (a.start == b.start) {
return a.end - b.end;
}
return a.start - b.start;
}
});

List<Interval> res = new ArrayList<>();
int i = 1;
Interval temp = intervals.get(0);
while (i < len) {
while (i < len && intervals.get(i).start <= temp.end) {
temp.start = Math.min(intervals.get(i).start, temp.start);
temp.end = Math.max(intervals.get(i).end, temp.end);
i++;
}