Meeting Room

来源：Facebook Phone Interview (2/12/2015)

原帖：http://www.fgdsb.com/2015/01/30/meeting-rooms/

题目 1：
write a function that detects conflicts in meeting schedules.

input: a list of schedules [(s1, e1), (s2, e2), ]

output: return True if there's any conflict, and False otherwise

代码：

 struct Interval {  
   double start;  
   double end;  
   Interval(double a, double b) : start(a), end(b) {}  
 };  
   
 bool compare(const Interval& a, const Interval& b) {  
   return a.start < b.start;  
 }  
   
 const double eps = 1.0e-12;  
 int compareDoulbe(double a, double b) {  
   if (b == 0) b += eps;  
   if (a == 0) a += eps;  
   double err = (a-b)/b; // a/b - 1;  
   return err > eps ? 1 : err < -eps ? -1 : 0;   
 }  
   
 bool existConflict(vector<Interval>& meetings) {  
   if (meetings.empty()) return false;  
   sort(meetings.begin(), meetings.end(), compare);  
   int N = meetings.size();  
   for (int i = 1; i < N; ++i) {  
     if (compareDouble(meetings[i].start, meetings[i-1].end)) {  
       return true;  
     }  
   }  
   return false;  
 }  

// test case
// {}, {{1.0,2.0}, {2.5, 3.5}, {5.2, 6.0}, }
// {{1.0, 5.0}, {3.6, 9.0}}

题目 2：

write a function that finds the minimum number of rooms that can accommodate given schedules.

代码：http://www.fgdsb.com/2015/01/30/meeting-rooms/

 bool compare(const pair<int,int>& a, const pair<int, int>& b) {  
   if (a.first == b.first) {  
     return a.second > b.second;  
   }  
   return a.first < b.first;  
 }  
   
 int minimumRoom(vector<Interval>& meetings) {  
   if (meetings.empty()) return 0;  
   vector<pair<int,int> > arrays;  
   for (int i = 0; i < meetings.size(); ++i) {  
     arrays.push_back(meetings[i].start, 0);  //可以使用start, -end来代替pair
     arrays.push_back(meetings[i].end, 1);  
   }  
   sort(arrays.begin(), arrays.end(), compare); //  
   int min = 0, res = 0;  
   for (int i = 0; i < arrays.size(); ++i) {  
     if (arrays[i].second == 0) {  
       min++;  
     } else {  
       min--;  
     }  
     res = max(min, res);  
   }  
   return res;   
 }  

另外一份代码：

 int min_rooms(vector<Interval>& meetings) {  
   vector<int> times;  
   for(auto m : meetings) {  
     times.push_back(m.begin);  
     times.push_back(-m.end);  
   }    
   sort(times.begin(), times.end(), [](int a, int b){  
     return abs(a) == abs(b) ? a < b : abs(a) < abs(b);  
   });    
   int ret = 0, cur = 0;  
   for(auto t : times) {  
     if(t >= 0) ret = max(ret, ++cur);  
     else --cur;  
   }  
   return ret;  
 }  

// test case

// {}, {{1.0, 3.0}, {3.5, 5.0}, {6.8, 10.0}} return 1 

// {{1.0, 8.0}, {2.0,6.0},{3.0, 7.0}} return 3 // 

// {{1.0, 4.0}, {2.0, 7.0}, {5.0, 8.0}} return 2;