跳转至

```c++ #include

include

include

include

include

include

include

using namespace std;

class ExamRoom { public: using CmpFunctionType = bool (*)(pair, pair); unordered_map> leftIntervalMap; unordered_map> rightIntervalMap;

Text Only
1
2
set<pair<int, int>> pq;
int N;

private:

Text Only
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void addInterval(pair<int, int> interval) {
    pq.insert(interval);
    leftIntervalMap[interval.first] = interval;
    rightIntervalMap[interval.second] = interval;
}

void removeInterval(pair<int, int> interval) {
    pq.erase(interval);
    leftIntervalMap.erase(interval.first);
    rightIntervalMap.erase(interval.second);
}

int distance(pair<int, int> interval) {
    int x = interval.first;
    int y = interval.second;
    if (x == -1) {
        return y;
    }
    if (y == N) {
        return N - x - 1;
    }
    return (y - x) / 2;
}

public: ExamRoom(int n) { this->N = n; auto cmp = this { auto distA = distance(a); auto distB = distance(b); if (distA == distB) { return a.first > b.second; }

Text Only
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
        return distA < distB;
        return true;
    };
    pq = set<pair<int, int>, decltype(cmp)>(cmp);

    auto mPair = std::make_pair(-1, n);
    addInterval(mPair);
}

int seat() {
    auto longest = *pq.rbegin();
    int x = longest.first;
    int y = longest.second;

    int seat = 0;
    if (x == -1) {
        seat = 0;
    } else if (y == N) {
        seat = N - 1;
    } else {
        seat = (y - x) / 2 + x;
    }

    auto left = std::make_pair(x, seat);
    auto right = std::make_pair(seat, y);
    removeInterval(longest);
    addInterval(left);
    addInterval(right);
    return seat;
}

void leave(int p) {
    auto left = leftIntervalMap[p];
    auto right = rightIntervalMap[p];

    auto merged = std::make_pair(left.first, right.second);
    removeInterval(left);
    removeInterval(right);
    addInterval(merged);
}

};

/ * Your ExamRoom object will be instantiated and called as such: * ExamRoom obj = new ExamRoom(n); * int param_1 = obj->seat(); * obj->leave(p); / int main() { printf(“hello world n“);

} ```