Daily LeetCode – day0154 0855. Exam Room

import java.util.TreeSet;

// 0855. Exam Room
class ExamRoom {

    int capacity;
    TreeSet<Integer> seats;

    public ExamRoom(int n) {
        this.capacity = n;
        this.seats = new TreeSet<>();
    }

    public int seat() {
        int seatNumber = 0;
        if (seats.size() > 0) {
            Integer prev = null;
            int distance = seats.first();
            for (Integer seat : seats) {
                if (prev != null) {
                    int d = (seat - prev) / 2;
                    if (distance < d) {
                        distance = d;
                        seatNumber = prev + distance;
                    }
                }
                prev = seat;
            }
            if (distance < capacity - 1 - seats.last()) {
                seatNumber = capacity - 1;
            }
        }
        seats.add(seatNumber);
        return seatNumber;
    }

    public void leave(int p) {
        seats.remove(p);
    }
}
学习笔记:
这是一道TreeSet的应用题,设计题。
其实就是该用这个数据结构,知道了之后就差需要进行分类讨论每次把新的学生分配到几号座位这个问题了。
第一个位置、最后一个位置,很容易会被忽视,一定要特殊处理。


关于樊轶群

一个善良的理想主义者。
此条目发表在每日LeetCode分类目录。将固定链接加入收藏夹。

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注