Meeting Rooms II

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), find the minimum number of conference rooms required.

For example,
Given [[0, 30],[5, 10],[15, 20]],
return 2.

Greedy, Sort

    public int minMeetingRooms(Interval[] intervals) {
        if(intervals.length == 0) return 0;

        int min = 0;
        Set<Interval> set = new LinkedHashSet();
        Arrays.sort(intervals, new Comparator<Interval>(){
            public int compare(Interval i1, Interval i2){
                if(i1.start == i2.start) return 0;
                else return i1.start > i2.start ? 1 : -1;
            }
        });

        for(Interval i : intervals)
            set.add(i);

        while(!set.isEmpty()){
            min ++;
            Iterator<Interval> iter = set.iterator();
            Interval head = iter.next();
            Interval prev = head;
            while(iter.hasNext()){
                Interval curr = iter.next();
                if(prev.end <= curr.start){
                    iter.remove();
                    prev = curr;
                }
            }
            set.remove(head);
        }

        return min;
    }

results matching ""

    No results matching ""