253. Meeting Rooms II

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

Example 1:

Input: [[0, 30],[5, 10],[15, 20]]
Output: 2
Example 2:

Input: [[7,10],[2,4]]
Output: 1

Solution

注意点:
1. 对于容器,如何在循环中修改元素的值

Complexity

Worst O(N2)
Best O(N)

Code

public int minMeetingRooms(int[][] intervals) {
        if(intervals == null || intervals.length == 0)
            return 0;
        Arrays.sort(intervals, new Comparator<int[]>(){
            public int compare(int[] i1, int[] i2){
                return i1[0] - i2[0];
            }
        });

        List<Integer> ends = new ArrayList<>();
        for(int[] interval : intervals){
            boolean isFound = false;
            ListIterator<Integer> iterator = ends.listIterator();
            while(iterator.hasNext()){
                Integer end = iterator.next();
                if(interval[0] >= end){
                    iterator.set(interval[1]);
                    isFound = true;
                    break;
                }
            }
            if(!isFound) ends.add(interval[1]);
        }
        return ends.size();
    }