BiruLyu
7/26/2017 - 11:01 PM

57. Insert Interval(#).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; }
* }
*/
// if output is total interval time, then array should be sorted to get the time
// if output should be sorted, we may need to sort the array
// if output should be not overlapping, we may need to merge intervals

// input: unsorted, no overlaps; output: can be unsorted, return total time; O(n) time, O(n) space
public class Solution {
public int insert(List<Interval> intervals, Interval newInterval) {
if (newInterval == null) {
return 0;
}
int totalTime = 0;
//if you need to insert intervals while calculating time,add:
//List<Interval> res = new ArrayList<>();
for (int i = 0; i < intervals.size(); i++) {
if (intervals.get(i).start <= newInterval.end || intervals.get(i).end >= newInterval.start) {//merge overlaps
newInterval.start = Math.min(newInterval.start, intervals.get(i).start);//remember to update the start!!!
newInterval.end = Math.max(newInterval.end, intervals.get(i).end);
} else {
totalTime += intervals.get(i).end - intervals.get(i).start;
}
}
totalTime += newInterval.end - newInterval.start;//we add the time of merged newInterval here
//if you need to insert intervals while calculating time,add:
//res.add(newInterval);//add the newInterval when all intervals have been checked so that no overlap exists
}
}

// input: unsorted, no overlaps; output: can be unsorted; O(n) time, O(1) space
public class Solution {
public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
if (newInterval == null) {
return intervals;

List<Interval> res = new ArrayList<>();
for (int i = 0; i < intervals.size(); i++) {
if (intervals.get(i).start <= newInterval.end || intervals.get(i).end >= newInterval.start) {//merge overlaps
newInterval.start = Math.min(newInterval.start, intervals.get(i).start);//remember to update the start too!!!
newInterval.end = Math.max(newInterval.end, intervals.get(i).end);
} else {
}
}
res.add(newInterval);//add the newInterval when all intervals have been checked so that no overlap exists
return res;
}
}

// input: sorted, no overlaps; output should be sorted; O(n) time, O(1) space
public class Solution {
public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
if (newInterval == null) {
return intervals;
}
// if the input is unsorted, add: (which will make this algo O(nlogn) time)
// Collections.sort(intervals, new Comparator<Interval>(){
//     public int compare(Interval a, Interval b) {
//         return a.start - b.start;
//     }
// });
List<Interval> res = new ArrayList<>();
int i = 0;
while (i < intervals.size() && intervals.get(i).end < newInterval.start) {
}//then we try to merge all intervals that can be merged
while (i < intervals.size() && intervals.get(i).start <= newInterval.end) {//not intervals.get(i).end>=newInterval.end
newInterval.start = Math.min(newInterval.start, intervals.get(i).start);//remember to update the start !!!
newInterval.end = Math.max(newInterval.end, intervals.get(i++).end);
}
while (i < intervals.size()) {
}
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> insert(List<Interval> intervals, Interval newInterval) {
List<Interval> res = new ArrayList<>();
if (intervals == null) return res;
int len = intervals.size();
int i = 0;
while (i < len && intervals.get(i).end < newInterval.start) {
}
while (i < len && intervals.get(i).start <= newInterval.end ) {
newInterval.start = Math.min(intervals.get(i).start, newInterval.start);
newInterval.end = Math.max(intervals.get(i).end, newInterval.end);
i++;
}
while (i < len) {
}
return res;
}
}``````