Notes: from others

Meeting room
facebook
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: false

Follow 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
LinkedIn
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;
}