855. Exam Room (Medium)

https://leetcode.com/problems/exam-room/

In an exam room, there are N seats in a single row, numbered 0, 1, 2, ..., N-1.

When a student enters the room, they must sit in the seat that maximizes the distance to the closest person.  If there are multiple such seats, they sit in the seat with the lowest number.  (Also, if no one is in the room, then the student sits at seat number 0.)

Return a class ExamRoom(int N) that exposes two functions: ExamRoom.seat() returning an int representing what seat the student sat in, and ExamRoom.leave(int p) representing that the student in seat number p now leaves the room.  It is guaranteed that any calls to ExamRoom.leave(p) have a student sitting in seat p.

 

Example 1:

Input: ["ExamRoom","seat","seat","seat","seat","leave","seat"], [[10],[],[],[],[],[4],[]]
Output: [null,0,9,4,2,null,5]
Explanation:
ExamRoom(10) -> null
seat() -> 0, no one is in the room, then the student sits at seat number 0.
seat() -> 9, the student sits at the last seat number 9.
seat() -> 4, the student sits at the last seat number 4.
seat() -> 2, the student sits at the last seat number 2.
leave(4) -> null
seat() -> 5, the student sits at the last seat number 5.

​​​​​​​

Note:

  1. 1 <= N <= 10^9
  2. ExamRoom.seat() and ExamRoom.leave() will be called at most 10^4 times across all test cases.
  3. Calls to ExamRoom.leave(p) are guaranteed to have a student currently sitting in seat number p.

Solutions

class ExamRoom {
    // It's not efficient to maintain the status of every seat. The better way is to keep
    // all the available ranges with vacancies. For instance, N=10, execute first seat
    // command, seat 0 is taken. Then available range is [1:9]; execute second seat
    // command, seat 9 is taken. The available range is [1:8]; execute third seat
    // command, seat 5 taken, then available ranges are [1:4] and [6,8]. For the later
    // operations, just repeat above procession. Once student on seat x leaves, merge the
    // two neighbor ranges. Remove the neighbor ranges and keep the newly merge bigger one.

    private int N;

    // use PriorityQueue to keep the maximum distance to closest person of ranges in descending order

    // private Queue<Integer> sortedDist = new PriorityQueue<>((o1, o2) -> o2 - o1);

    // Never use above expression, otherwise may cause overflow.
    // For instance, o2 = 2147483647 and o1 = -2147483648

    private Queue<Integer> sortedDist = new PriorityQueue<>(Comparator.reverseOrder());

    // a bunch of ranges could have same maximum distance, so the map is 1->n, and the problem requires
    // that the ranges in the front is of higher priority. so we use PriorityQueu to sort the ranges of
    // same maximum distance.
    private Map<Integer, PriorityQueue<Integer>> dist2RangeHeadMap = new HashMap<>();

    // anchor for particular range, locating by head index
    private Map<Integer, Range> head2RangeMap = new HashMap();

    // anchor for particular range, locating by tail index
    private Map<Integer, Range> tail2RangeMap = new HashMap();

    public ExamRoom(int N) {
        this.N = N;
    }

    public int seat() {
        if (dist2RangeHeadMap.size() == 0) {
            Range range = new Range(1, N - 1);

            addRange(range);

            return 0;
        }

        int maxRange = sortedDist.peek();
        int rangeHead = dist2RangeHeadMap.get(maxRange).peek();
        Range range = head2RangeMap.get(rangeHead);
        int seat = range.seat;

        // remove range at first
        removeRange(range);

        // split current range into two sub range

        // left neighbor range
        Range range1 = new Range(rangeHead, seat - 1);
        if (range1.maxDist >= 1) {
            addRange(range1);
        }

        // right neighbor range
        Range range2 = new Range(seat + 1, range.tail);
        if (range2.tail < N && range2.maxDist >= 1) {
            addRange(range2);
        }

        return seat;
    }

    public void leave(int p) {
        int leftRangeTail = p - 1;
        int rightRangeHead = p + 1;

        Range leftRange = null;
        Range rightRange = null;

        // combine neighbor ranges
        if (tail2RangeMap.containsKey(leftRangeTail)) {
            leftRange = tail2RangeMap.get(leftRangeTail);
        }
        if (head2RangeMap.containsKey(rightRangeHead)) {
            rightRange = head2RangeMap.get(rightRangeHead);
        }

        if (leftRange == null && rightRange == null) {
            Range range = new Range(p, p);
            addRange(range);
        }

        // delete neighbor ranges
        if (leftRange != null) {
            removeRange(leftRange);
        }

        if (rightRange != null) {
            removeRange(rightRange);
        }

        if (leftRange != null && rightRange == null) {
            Range range = new Range(leftRange.head, p);
            addRange(range);
        }

        if (leftRange == null && rightRange != null) {
            Range range = new Range(p, rightRange.tail);
            addRange(range);
        }

        if (leftRange != null && rightRange != null) {
            Range range = new Range(leftRange.head, rightRange.tail);
            addRange(range);
        }
    }

    private void removeRange(Range range) {
        // remove this range
        dist2RangeHeadMap.get(range.maxDist).remove(range.head);

        // remove the head of this range
        head2RangeMap.remove(range.head);

        // remove the tail of this range
        tail2RangeMap.remove(range.tail);

        // the max range is unique
        if (dist2RangeHeadMap.get(range.maxDist).size() == 0) {
            sortedDist.remove(range.maxDist);
        }
    }

    private void addRange(Range range) {
        if (!sortedDist.contains(range.maxDist)) {
            sortedDist.offer(range.maxDist);
        }

        if (!dist2RangeHeadMap.containsKey(range.maxDist)) {
            dist2RangeHeadMap.put(range.maxDist, new PriorityQueue<>());
        }
        dist2RangeHeadMap.get(range.maxDist).offer(range.head);

        head2RangeMap.put(range.head, range);

        tail2RangeMap.put(range.tail, range);
    }

    class Range {
        // the start position of the range
        public int head;

        // the end position of the range
        public int tail;

        // the size of the range
        public int size;

        // the best seat of the range, could be the middle or head or tail
        public int seat;

        // from head to seat, or seat to tail, the max distance it can be
        // to closest people. think seriously about both odd or even size
        // of range.
        public int maxDist;

        public Range(int head, int tail) {
            this.head = head;
            this.tail = tail;
            this.size = tail - head + 1;

            // the range starts from 0
            if (head == 0) {
                seat = 0;
                maxDist = tail - seat + 1;
            } else if (tail == N - 1) { // range ends at N-1
                seat = N - 1;
                maxDist = seat - head + 1;
            } else { // above two are special cases, this is ordinary one which chooses the middle
                seat = (int)((tail * 1l + head * 1l) / 2);
                maxDist = Math.min(seat - head + 1, tail - seat + 1);
            }
        }

        // rewrite following two functions
        @Override
        public boolean equals(Object o) {
            if (!(o instanceof Range)) {
                return false;
            }

            Range r = (Range) o;

            return r.head == head && r.tail == tail;
        }

        @Override
        public int hashCode() {
            return (head + "#" + tail).hashCode();
        }
    }
}

Incorrect Solutions

References

Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2019-12-03 11:01:18

results matching ""

    No results matching ""