ref: http://www.fgdsb.com/2015/01/30/meeting-rooms/
Given a array of pairs where each pair contains the start and end time of a meeting (as in int),
Determine if a single person can attend all the meetings
For example:
Input array{ pair(1,4), pair(4, 5), pair(3,4), pair(2,3) }
Output: falseFollow up:
determine the minimum number of meeting rooms needed to hold all the meetings.
Input array{ pair(1, 4), pair(2,3), pair(3,4), pair(4,5) }
Output: 2
Follow up题也可以换一种形式:
Giving lots of intervals [ai, bi], find a point intersect with the most number of intervals
和Insert/Merge Intervals也属于一类题。
按start排序,找overlap
follow up:
#1 把所有interval的开始和结束点提取出来,vector<int> 里进行排序
#2 遇到开始 + 1,结束 - 1
类似于按时间轴进行扫描,在某一个时间点覆盖最多的interval的数量,为最大的需要房间数量
------------------------------------------------------------------
ZigZag iterator
ref: http://www.fgdsb.com/2015/01/30/zigzag-iterator/#more
以下代码可用于k个iterator
class ZigZagIterator() { ZigZagIterator(vector<Iterator> &itrs) { this->itrs = itrs; pointer = 0; if (!itrs[pointer].hasNext()) setNextAvailable(); } void setNextAvailable() { int old = pointer; while (true) { pointer++; pointer %= itrs.size(); if (itrs[pointer].hasNext()) { return; } if (pointer == old) { pointer = -1; return; } } } bool hasNext() { return pointer == -1; } int next() { int ret = itrs[pointer]; setNextAvailable(); return ret; } private: vector<Iterator> itrs; int pointer; };
------------------------------------------------------------------------------------
Factor Combination
ref: http://www.fgdsb.com/2015/01/27/factor-combinations/
dfs
void helper(vector<vector<int>> &rt,int n,vector<int> &cur,int start) { if (n == 1) { vector<int> t = cur; rt.push_back(t); return; } for (int i = start; i <= n; i++) { if (n % i != 0) continue; cur.push_back(i); helper(rt,n / i,cur,i); cur.pop_back(); } } vector<vector<int>> factorComb(int n) { vector<vector<int>> rt; vector<int> cur; helper(rt,n,cur,2); rt.pop_back(); return rt; }
No comments:
Post a Comment