【设计】855. 考场就座

855. 考场就座

这段代码实现了一个考场安排座位的算法。在这个算法中，考场被模拟成一个从0到n-1的数轴，其中每个位置代表一个座位。目的是在每次学生入座时，找到一个使得所有学生之间距离最大化的座位，并在学生离开时更新座位信息。下面是具体的实现思路和算法描述：

1. 初始化 (public ExamRoom(int n)):

   • n：考场座位的总数。
   • intervals：一个TreeSet，用于存储当前所有空闲区间，并按照某种规则排序。这里的排序规则首先比较两个区间可坐的最远距离，如果相同，则比较区间的末端位置。
   • startToInterval和endToInterval：两个HashMap，分别用于快速定位一个区间的开始和结束位置对应的区间对象。
   • 在初始化时，会添加一个特殊区间[-1, n]到intervals中，表示整个考场最开始时全部为空。

2. 入座 (public int seat()):

   • 从intervals中取出最优区间（即开始时的排序规则确定的第一个区间），然后根据该区间的起始位置和结束位置计算出新的座位位置。
   • 如果该区间的起始位置是-1，说明最左侧是空的，因此新的座位位置是0。
   • 如果该区间的结束位置是n，说明最右侧是空的，因此新的座位位置是n-1。
   • 否则，新的座位位置是区间中点。
   • 入座后，将原区间分为两个新区间，并加入到intervals中。

3. 离开 (public void leave(int p)):

   • 当一个学生离开座位时，通过endToInterval和startToInterval找到该座位所属的两个区间。
   • 将这两个区间合并为一个新区间，并更新到intervals中。

4. 辅助方法:

   • private void removeInterval(int[] interval)：从intervals、startToInterval和endToInterval中移除指定区间。
   • private void addInterval(int[] interval)：向intervals、startToInterval和endToInterval中添加新区间。
   • private int dist(int[] interval)：计算一个区间中可以坐的最远距离。如果区间的起始或结束是边界，距离计算方式略有不同。

通过上述方法，该算法能够有效地在每次学生入座时找到最优的座位，并在学生离开时更新座位信息，以保证考场的座位安排尽可能地公平和高效。

class ExamRoom {int n;TreeSet<int[]> intervals;HashMap<Integer, int[]> startToInterval;HashMap<Integer, int[]> endToInterval;public ExamRoom(int n) {this.n = n;startToInterval = new HashMap<>();endToInterval = new HashMap<>();intervals = new TreeSet<>((a, b) ->dist(b)  != dist(a) ?  dist(b) - dist(a) : a[1] - b[1]);addInterval(new int[]{-1, n});}public int seat() {int[] interval  = intervals.pollFirst();int start = interval[0];int end = interval[1];int seat = 0;if (start == -1) {seat = 0;} else if (end == n) {seat = n - 1;} else {seat = (start + end) >>> 1;}addInterval(new int[]{start, seat});addInterval(new int[]{seat, end});return seat;}public void leave(int p) {int[] i1 = endToInterval.get(p);int[] i2 = startToInterval.get(p);int start = i1[0];int end = i2[1];int[] interval = new int[]{start, end};removeInterval(i1);removeInterval(i2);addInterval(interval);}private void removeInterval(int[] interval) {intervals.remove(interval);startToInterval.remove(interval[0]);endToInterval.remove(interval[1]);}private void addInterval(int[] interval) {intervals.add(interval);startToInterval.put(interval[0], interval);endToInterval.put(interval[1], interval);}private int dist(int[] interval) {int start = interval[0];int end = interval[1];if (start == -1 || end == n) {return end - start - 1;}return (end - start) / 2;}
}/*** Your ExamRoom object will be instantiated and called as such:* ExamRoom obj = new ExamRoom(n);* int param_1 = obj.seat();* obj.leave(p);*/