1847. 最近的房间

注意sort时，自定义函数要加引用

lower_bound用set自己的

set是用红黑树存的，所以lower_bound时会用自己的结构查找

class Solution {
public:
    

struct node
{
    int x, y;
    bool operator < (const node b) const{
        return y < b.y;
    }
}Node[100010];
struct edge{
    int x, y;
    bool operator < (const edge b) const {
        return x < b.x;
    }
};
    int tmp[100100];
    set ss;
    vector<int> closestRoom(vectorint>>& rooms, vectorint>>& queries) {
        vector<int> ret;
        int n = rooms.size();
        int m = queries.size();
        for(int i = 0; i < n; i++)
        {
            Node[i].x = rooms[i][0];
            Node[i].y = rooms[i][1];
        }
        for(int i = 0; i < m; i++)
            queries[i].push_back(i);
        sort(Node, Node + n);
        sort(queries.begin(), queries.end(), [](vector<int>& a, vector<int>& b)->bool{ return a[1] > b[1];});
        int t = n;
        // for(int i = 0; i < n; i++)
        //     cout << Node[i].x << "  " << Node[i].y << endl;


        for(int i = 0; i < m; i++)
        {
            node u;
            u.x = queries[i][0];
            u.y = queries[i][1];

            int k = lower_bound(Node, Node + n, u) - Node;
            if(k == n) tmp[queries[i][2]] = -1;
            else
            {
                for(int j = k; j < t; j++)
                {
                    edge v;
                    v.x = Node[j].x;
                    v.y = Node[j].y;
                    ss.insert(v);
                }
                t = k;
                edge r;
                r.x = u.x;
                r.y = u.y;
                set::iterator it = ss.lower_bound(r);
                // for(set::iterator it = ss.begin(); it != ss.end(); it++)
                // cout << (*it).x << "  " << (*it).y << endl;
                if(it == ss.end())
                {
                    it--;
                    tmp[queries[i][2]] = (*it).x;
                }   
                else if(it != ss.begin())
                {
                    int value = abs((*it).x - r.x);
                    int id = (*it).x;
                    it--;
                    if(value >= abs((*it).x - r.x))
                        id = (*it).x;
                    tmp[queries[i][2]] = (id);
                }
                else tmp[queries[i][2]] = (*it).x;
            }


        }
        for(int i = 0; i < m; i++)
            ret.push_back(tmp[i]);

    return ret;

        

    }
};