11/23 Google Intern Interview

tanpf5 发表于 2015-12-3 00:36
我记得当时我问过这个问题，相等不算重叠，不删除

那相等的情况就得merge吧，[2, 4], [4, 6]变成[2, 6]？

bobzhang2004 发表于 2015-12-3 00:50
那相等的情况就得merge吧，[2, 4], [4, 6]变成[2, 6]？

这题是去掉重叠的而已，不合并

bobzhang2004 发表于 2015-12-3 00:50
那相等的情况就得merge吧，[2, 4], [4, 6]变成[2, 6]？

这题是去掉重叠的而已，不合并

根据楼主的意思，重新改了下代码，谢谢

1. public class MergeIntervalsIII {
   
2.         public static void main(String[] args) {
   
3.                 List<Interval> intervals = new ArrayList<Interval>();
   
4.                 intervals.add(new Interval(4, 8));
   
5.                 intervals.add(new Interval(3, 4));
   
6.                 intervals.add(new Interval(-1, 2));
   
7.                 intervals.add(new Interval(10, 12));
   
8. 
   
9.                 List<Interval> res = mergeIntervals(intervals);
   
10.                 for (Interval interval : res) {
    
11.                         System.out.println(interval.start + " " + interval.end);
    
12.                 }
    
13.         }
    
14.        
    
15.         static class Interval {
    
16.                 int start;
    
17.                 int end;
    
18. 
    
19.                 Interval() {
    
20.                         start = 0;
    
21.                         end = 0;
    
22.                 }
    
23.                 Interval(int s, int e) {
    
24.                         start = s;
    
25.                         end = e;
    
26.                 }
    
27.         }
    
28.        
    
29.         /*
    
30.                  intervals.add(new Interval(4, 8));
    
31.                 intervals.add(new Interval(3, 5));
    
32.                 intervals.add(new Interval(-1, 5));
    
33.                 intervals.add(new Interval(10, 12));
    
34.                 这个case 应该是返回(10, 12)
    
35.          */
    
36.         public static List<Interval> mergeIntervals(List<Interval> intervals) {
    
37.                 List<Interval> res = new ArrayList<Interval>();
    
38.                 if (intervals == null || intervals.size() == 0) {
    
39.                         return res;
    
40.                 }
    
41.                 Collections.sort(intervals, new Comparator<Interval>(){
    
42.                         public int compare(Interval i1, Interval i2) {
    
43.                                 if (i1.start == i2.start) {
    
44.                                         return i1.end - i2.end;
    
45.                                 }
    
46.                                
    
47.                                 return i1.start - i2.start;
    
48.                         }
    
49.                 });
    
50.                 List<Interval> list = new ArrayList<Interval>();
    
51.                 boolean[] isOverlap = new boolean[intervals.size()];
    
52.                 list.add(intervals.get(0));
    
53.                 for (int i = 1; i < intervals.size(); i++) {
    
54.                         if (intervals.get(i).start < list.get(list.size() - 1).end) {
    
55.                                 isOverlap[i] = true;
    
56.                                 isOverlap[i - 1] = true;
    
57.                                 list.get(list.size() - 1).end = Math.max(list.get(list.size() - 1).end, intervals.get(i).end);
    
58.                         } else {
    
59.                                 list.add(intervals.get(i));
    
60.                         }
    
61.                 }
    
62.                 for (int i = 0; i < intervals.size(); i++) {
    
63.                         if (!isOverlap[i]) {
    
64.                                 res.add(intervals.get(i));
    
65.                         }
    
66.                 }
    
67.                 return res;
    
68.         }
    
69. }
    

复制代码