Insert Interval
给一个interval list和一个interval, 插入到list中. 这个题好难…
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 35 |
/** * 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<Interval>(); if(intervals.size() == 0){ res.add(newInterval); return res; } int i = 0; while(i < intervals.size() && intervals.get(i).end < newInterval.start){ res.add(intervals.get(i)); i++; } if(i < intervals.size()) newInterval.start = Math.min(newInterval.start, intervals.get(i).start); res.add(newInterval); while(i < intervals.size() && intervals.get(i).start <= newInterval.end){ newInterval.end = Math.max(newInterval.end, intervals.get(i).end); i++; } while(i < intervals.size()){ res.add(intervals.get(i)); i++; } return res; } } |