public List<Interval> insert(List<Interval> intervals, Interval newInterval) {

int start = newInterval.start;

int end = newInterval.end;

List<Interval> result = new ArrayList<>();

boolean newAdded = false;

for (Interval in: intervals) {

if (in.end < start) {

result.add(in);

} else if (in.start > end) {

if (!newAdded) {

result.add(new Interval(start, end));

newAdded = true;

}

result.add(in);

} else {

start = Math.min(in.start, start);

end = Math.max(in.end, end);

}

}

if (!newAdded) {

result.add(new Interval(start, end));

}

return result;

}

public static void main(String[] args) {

InsertInterval57 ii = new InsertInterval57();

System.out.println(ii.insert(new ArrayList<Interval>(Arrays.asList(new Interval(1, 3), new Interval(6, 9))), new Interval(2, 5)));

}