LintCode 919: Meeting Rooms II (掃描線算法經典題)

1. 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.

Example

Given intervals = [(0,30),(5,10),(15,20)], return 2.

思路：掃描線算法。

1. 把所有的事件，包括開始和結束都放到一起排序。
2. 如果結束時間和開始時間在一起，兩個都要算。是以在operator()中，如果a和b的時間一樣則按事件類型排序(eventStart<eventEd)

代碼如下：

/**
 * Definition of Interval:
 * classs Interval {
 *     int start, end;
 *     Interval(int start, int end) {
 *         this->start = start;
 *         this->end = end;
 *     }
 * }
 */

struct event {
    int eventTime;
    int eventType;  //start = 0, end = 1
    event(int eTime, int eType) : eventTime(eTime), eventType(eType) {}
};

struct cmp {
    bool operator () (event & a, event &b) {
        if (a.eventTime < b.eventTime) {
            return true;
        } else if (a.eventTime == b.eventTime) {
            return a.eventType < b.eventType;
        } else {
            return false;
        }
    }    
} compare;


class Solution {
public:
    /**
     * @param intervals: an array of meeting time intervals
     * @return: the minimum number of conference rooms required
     */
    int minMeetingRooms(vector<Interval> &intervals) {
        int intervalSize = intervals.size();
        if (intervalSize == 0) return 0;
        
        vector<event> events;
        int count = 0;
        int maxCount = 0;
        for (int i = 0; i < intervalSize; ++i) {
            events.push_back(event(intervals[i].start, 0));
            events.push_back(event(intervals[i].end, 1));
        }
        sort(events.begin(), events.end(), compare);
        
        int eventSize = events.size();
        for (int i = 0; i < eventSize; ++i) {
            if (events[i].eventType == 0) {
                count++;
                maxCount = max(maxCount, count);
            } else {
                count--;
            }
        }
        
        return maxCount;
    }
};