Meeting Room

lc252

判读这个人能否参加所有的会议。 skyline problem， 把intervals拆分成点。

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */


public class Solution {
    public boolean canAttendMeetings(Interval[] intervals) {
        if(intervals == null || intervals.length == 0) return true;
        Arrays.sort(intervals, new Comparator<Interval>(){
            public int compare(Interval i1, Interval i2){
                return i1.start - i2.start;
            }
        });
        int end = intervals[0].end;
        for(int i = 1; i < intervals.length; i++){
            if(intervals[i].start < end) {
                return false;
            }
            end = Math.max(end, intervals[i].end);
        }
        return true;
    }
}

lc 253 meeting room 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.

time complexity:

o(n) iterate the array, however, we use heap to sort the result, so if should be nlogn. Space o(n)

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class Solution {

    class Point{
        int val;
        int flag;
        public Point(int val, int flag){
            this.val = val;
            this.flag = flag;
        }
    }    

    public int minMeetingRooms(Interval[] intervals) {
        if(intervals == null || intervals.length == 0) return 0;
        PriorityQueue<Point> queue = new PriorityQueue<Point>(intervals.length, new Comparator<Point>(){
            public int compare(Point a, Point b){
                if(a.val== b.val){
                    return b.flag - a.flag;
                }
                return a.val - b.val;
            }
        });

        for(int i = 0; i < intervals.length; i++){

            queue.offer(new Point(intervals[i].start, 0));
            queue.offer(new Point(intervals[i].end, 1));            
        }
        int count = 0;
        int res = 0;
        while( !queue.isEmpty()){

            Point cur = queue.poll();
            if(cur.flag == 0){
                count++;
            }else{
                count--;
            }
            if(count > res) {
                res = count;
            }
        }
        return res; 

    }
}

打印所有的room

public class Solution {

    class Point{
        int val;
        int flag;
        Intervals interval;
        public Point(int val, int flag, Intervals interval){
            this.val = val;
            this.flag = flag;
            this.interval = interval;
        }
    }



    public int minMeetingRooms(Interval[] intervals) {
        if(intervals == null || intervals.length == 0) return 0;
        PriorityQueue<Point> queue = new PriorityQueue<Point>(intervals.length, new Comparator<Point>(){
            public int compare(Point a, Point b){
                if(a.val== b.val){
                    return b.flag - a.flag;
                }
                return a.val - b.val;
            }
        });

        int res = 0;
        HashMap<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();
        HashMap<Intervals, Integer> map2 = new HashMap<Intervals, Integer>();
        ArrayList<Integer> list = new ArrayList<Integer>();
        int index = 1;
        map.put(1, new ArrayList<Integer>());

        for(int i = 0; i < intervals.length; i++){

            queue.offer(new Point(intervals[i].start, 0,intervals[i] ));
            queue.offer(new Point(intervals[i].end, 1,intervals[i]));

        }
        int count = 0;

        while( !queue.isEmpty()){

            Point cur = queue.poll();
            if(cur.flag == 0){
                if(list.size() != 0){
                    int k = list.get(0);
                    list.remove(0);
                    map.get(k).add(cur.interval);
                    map2.put(cur.interval, k);
                    count++;
                }else{
                    map.put(index, new ArrayList<Integer>());
                    map.get(index).add(cur.interval);
                    index++;
                    count++;

                }

            }else{
                int usedIndex = map2.get(cur.interval);
                list.add(usedIndex);
                count--;

            }
            if(count > res) {
                res = count;
            }
        }
        return res;

    }
}