package array; import java.util.ArrayList; import java.util.Arrays; import java.util.List; /** * Created by gouthamvidyapradhan on 15/12/2017. Given a set of non-overlapping intervals, insert a * new interval into the intervals (merge if necessary). * *
You may assume that the intervals were initially sorted according to their start times. * *
Example 1: Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9]. * *
Example 2: Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as * [1,2],[3,10],[12,16]. * *
This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10]. * *
Solution: O(n): Iterate through each interval and check for each overlapping case
*/
public class InsertInterval {
public static class Interval {
int start;
int end;
Interval() {
start = 0;
end = 0;
}
Interval(int s, int e) {
start = s;
end = e;
}
}
/**
* Main method
*
* @param args
* @throws Exception
*/
public static void main(String[] args) throws Exception {
Interval i1 = new Interval(1, 2);
Interval i2 = new Interval(3, 5);
Interval i3 = new Interval(6, 7);
Interval i4 = new Interval(8, 10);
Interval i5 = new Interval(12, 16);
List