html5微网站开发教程,c 网站开发框架,页面设计公司排名,网站做301打不开855. 考场就座
这段代码实现了一个考场安排座位的算法。在这个算法中#xff0c;考场被模拟成一个从0到n-1的数轴#xff0c;其中每个位置代表一个座位。目的是在每次学生入座时#xff0c;找到一个使得所有学生之间距离最大化的座位#xff0c;并在学生离开时更新座位信息…855. 考场就座
这段代码实现了一个考场安排座位的算法。在这个算法中考场被模拟成一个从0到n-1的数轴其中每个位置代表一个座位。目的是在每次学生入座时找到一个使得所有学生之间距离最大化的座位并在学生离开时更新座位信息。下面是具体的实现思路和算法描述 初始化 (public ExamRoom(int n)): n考场座位的总数。intervals一个TreeSet用于存储当前所有空闲区间并按照某种规则排序。这里的排序规则首先比较两个区间可坐的最远距离如果相同则比较区间的末端位置。startToInterval和endToInterval两个HashMap分别用于快速定位一个区间的开始和结束位置对应的区间对象。在初始化时会添加一个特殊区间[-1, n]到intervals中表示整个考场最开始时全部为空。 入座 (public int seat()): 从intervals中取出最优区间即开始时的排序规则确定的第一个区间然后根据该区间的起始位置和结束位置计算出新的座位位置。如果该区间的起始位置是-1说明最左侧是空的因此新的座位位置是0。如果该区间的结束位置是n说明最右侧是空的因此新的座位位置是n-1。否则新的座位位置是区间中点。入座后将原区间分为两个新区间并加入到intervals中。 离开 (public void leave(int p)): 当一个学生离开座位时通过endToInterval和startToInterval找到该座位所属的两个区间。将这两个区间合并为一个新区间并更新到intervals中。 辅助方法: 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;TreeSetint[] intervals;HashMapInteger, int[] startToInterval;HashMapInteger, 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);*/
