Maximum overlapping interval

Maximum overlapping interval

Given n intervals [si, fi], find the maximum number of overlapping intervals.

 Naive Thinking: 好像是讲greedy时候的题目。从对所有interval排序，如果si相同就按fi排序。然后用greedy的思想取第一个，接着取最接近却又不和第一个重合的，依次类推，直到不能取，这算是一层，然后同样的方法取第二层、第三层，直到所有的都被取了一遍，看有多少层。

如果用一个doubly linked list去存排好序的interval,就可以实现O(nlogn)的算法复杂度，否则，用数组遍历就是O(n^2)的算法复杂度。

import java.util.Set;
import java.util.HashSet;
import java.util.Comparator;
import java.util.Arrays;
import java.util.Iterator;

class Interval{
        int b;
        int e;
        Interval(int begin, int end){
            b = begin;
            e = end;
        }
    }
public class Solution{

    public static void main(String args[]){
        Solution s = new Solution();
        Interval[] intervals = new Interval[10];
        intervals[0] = new Interval(0, 3);
        intervals[1] = new Interval(2, 4);
        intervals[2] = new Interval(3, 6);
        intervals[3] = new Interval(4, 5);
        intervals[4] = new Interval(5, 9);
        intervals[5] = new Interval(7, 8);
        intervals[6] = new Interval(6, 7);
        intervals[7] = new Interval(9, 11);
        intervals[8] = new Interval(7, 13);
        intervals[9] = new Interval(3, 8);
        System.out.println(s.maxOverlapInterval(intervals));
    }

   

    public int maxOverlapInterval(Interval[] intervals){
        Set<Interval> set = new HashSet<Interval>();
        int layers = -1;
        int end = -1;
        Comparator<Interval> c = new Comparator<Interval>(){
            @Override
            public int compare(Interval x, Interval y){
                if(x.b < y.b){
                    return -1;
                }else if(x.b > y.b){
                    return 1;
                }else{
                    if(x.e < y.e){
                        return -1;
                    }else if(x.e > y.e){
                        return 1;
                    }
                }
                return 0;
            }
        };
        Arrays.sort(intervals, c);
        for(int i = 0;i < intervals.length;i++)
            set.add(intervals[i]);
        while(!set.isEmpty()){
            // Iterator<Interval> iter = set.iterator();
            // while(iter.hasNext()){
            //     Interval i = iter.next();
            //     if(i.b > end){
            //         set.remove(i);
            //         end = i.e;
            //     }
            // }
            for(int i = 0;i < intervals.length;i++){
                if(set.contains(intervals[i])){
                    if(intervals[i].b > end){
                        set.remove(intervals[i]);
                        end = intervals[i].e;
                    }
                }
            }
            end = -1;
            layers++;
        }
        return Math.max(layers,0);
    }
}