FG面经： Interval问题合集

How to insert interval to an interval list. List is not sorted

O(N) solution:

 1 package fb;
 2 import java.util.*;
 3 
 4 class Interval {
 5     int start;
 6     int end;
 7     public Interval(int s, int e) {
 8         start = s;
 9         end = e;
10     }
11 }
12 
13 
14 public class InsertInterval {
15 
16 
17     
18     public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
19 
20         ArrayList<Interval> res = new ArrayList<Interval>();
21         for (Interval interval : intervals) {
22             if (interval.end < newInterval.start || interval.start>newInterval.end) {
23                 res.add(interval);
24             }
25             else {
26                 newInterval.start = Math.min(newInterval.start, interval.start);
27                 newInterval.end = Math.max(newInterval.end, interval.end);
28             }
29         }
30         res.add(newInterval);
31         return res;
32     }
33     
34     /**
35      * @param args
36      */
37     public static void main(String[] args) {
38         // TODO Auto-generated method stub
39         InsertInterval sol = new InsertInterval();
40         Interval i1 = new Interval(1,3);
41         Interval i2 = new Interval(6,9);
42         Interval i3 = new Interval(100,102);
43         List<Interval> intervals = new ArrayList<Interval>();
44         intervals.add(i2);
45         intervals.add(i1);
46         intervals.add(i3);
47         List<Interval> res = sol.insert(intervals, new Interval(3,7));
48         for (Interval each : res) {
49             System.out.print(each.start);
50             System.out.println(each.end);
51         }
52     }
53 
54 }

两个interval overlap条件：

interval1.end >= interval2.start && interval1.start <= interval2.end

问：一个query数在不在已经加入的区间？

如果interval是sorted, 就可以binary search, 插入位置的上一个interval, 判断是否在那个interval里面

如果没有sorted, 只能挨个比了