这题应该清楚List是ArrayList还是LinkedList,ArrayList的话二分来查找更快,而LinkedList的话,直接线性遍历一遍即可。看了其他人的结题报告,基本线性一遍就可以过了。
然后注意各种边界条件即可:
1: newinterval 和intervals没有重合
2: newinterval和intervals重合。
import java.util.*; public class Solution { int bSearch(List<Interval> intervals, int val) { int n = intervals.size() ; if(val < intervals.get(0).start) { return -1; } else if(val > intervals.get(n-1).start) { return n-1; } int l = 0; int r = n-1; int m = -2; while(l<=r) { m = (l+r)>>1; if( intervals.get(m).start <= val && (m >= n -1 || val < intervals.get(m+1).start)) return m; else if(intervals.get(m).start > val) r = m -1; else l = m + 1; } return m; } public List<Interval> insert(List<Interval> intervals, Interval newInterval) { int n = intervals.size() ; if(n == 0) { intervals.add(newInterval); return intervals; } int kb = bSearch(intervals, newInterval.start); int ke = bSearch(intervals, newInterval.end); if(kb == ke) { if(kb == -1) intervals.add(0,newInterval); else if(newInterval.start > intervals.get(kb).end) intervals.add(kb+1,newInterval); else intervals.get(ke).end = (intervals.get(ke).end > newInterval.end) ? intervals.get(ke).end : newInterval.end; return intervals; } if(kb == -1) { kb++; intervals.get(0).start = newInterval.start; } else if(intervals.get(kb).end < newInterval.start) { kb++; intervals.get(kb).start = newInterval.start; } intervals.get(kb).end = (intervals.get(ke).end > newInterval.end) ? intervals.get(ke).end : newInterval.end; for(int i = kb+1;i<=ke;i++) { intervals.remove(kb+1); } return intervals; } public static void main(String[] args) { List<Interval> intervals = new ArrayList<Interval>(); intervals.add(new Interval(1,5)); intervals.add(new Interval(9,12)); intervals.add(new Interval(20,22)); Solution sol = new Solution(); sol.insert(intervals, new Interval(10,15)); for(Interval interval : intervals) { System.out.println(interval.start + " " + interval.end); } } }