391 Perfect Rectangle

class Solution {
public:
    int findPos(vector<vector<int>>& record, int y1) {
        int n = record.size();
        if ( record[0][0] == y1 ) return 0;
        if ( record[n-1][0] == y1 ) return n-1;
        int l = 0, r = n-1;
        while ( l < r-1 ) {
            int m = (l+r)/2;
            if ( record[m][0] == y1 ) return m;
            if ( y1 > record[m][0] ) l = m;
            else r = m;
        }
        return -1;
    }
    bool isRectangleCover(vector<vector<int>>& rectangles) {
        sort(rectangles.begin(), rectangles.end());
        vector<vector<int>> record;
        int n = rectangles.size();
        if ( n <= 1 ) return true;
        vector<int> tmp(3, 0);
        tmp[0] = rectangles[0][1]; tmp[1] = INT_MAX; tmp[2] = rectangles[0][0];
        record.push_back(tmp);
        for ( int i = 0; i < n; i++ ) {
            // [x1, y1, x2, y2] -> (y1, y2, x2)
            int x1 = rectangles[i][0], y1 = rectangles[i][1], x2 = rectangles[i][2], y2 = rectangles[i][3];
            tmp[0] = y1; tmp[1] = y2; tmp[2] = x2;
            int pos = findPos(record, y1);
            if ( pos == -1) return false;
            if ( x1 != record[pos][2] ) return false;
            if ( y2 > record[pos][1] ) return false;
            if ( y2 == record[pos][1] ) record[pos][2] = x2;
            else {
                record.insert(record.begin()+pos, tmp);
                record[pos+1][0] = y2;
            }
            // merge record[pos] with either record[pos-1] or record[pos+1]
            if ( pos < int(record.size())-1 and record[pos][2] == record[pos+1][2] ) {
                record[pos][1] = record[pos+1][1];
                record.erase(record.begin()+pos+1);
            }
            if ( pos > 0 and record[pos][2] == record[pos-1][2] ) {
                record[pos-1][1] = record[pos][1];
                record.erase(record.begin()+pos);
            }
        }
        return ( int(record.size()) == 2 );
    }
};

Notes
耶，漫长的第一遍刷完了呢！开心！
这题的思路和skyline那个问题有点像，把所有输入的矩形排序，然后维护一个类似skyline的东西来判断每个新加入的矩形有没有“不合法”。因为已经排序过，新加的矩形一定是贴着skyline的。然后根据新加的居心对skyline更新，直至最后。检查skyline的右边界是否合法。