729. My Calendar I

729. My Calendar I

Implement a MyCalendar class to store your events. A new event can be added if adding the event will not cause a double booking.

Your class will have the method, book(int start, int end). Formally, this represents a booking on the half open interval [start, end), the range of real numbers x such that start <= x < end.

A double booking happens when two events have some non-empty intersection (ie., there is some time that is common to both events.)

For each call to the method MyCalendar.book, return true if the event can be added to the calendar successfully without causing a double booking. Otherwise, return false and do not add the event to the calendar.

Your class will be called like this: MyCalendar cal = new MyCalendar(); MyCalendar.book(start, end)

Example 1:

MyCalendar();
MyCalendar.book(10, 20); // returns true
MyCalendar.book(15, 25); // returns false
MyCalendar.book(20, 30); // returns true
Explanation: 
The first event can be booked.  The second can't because time 15 is already booked by another event.
The third event can be booked, as the first event takes every time less than 20, but not including 20.

Note:

The number of calls to MyCalendar.book per test case will be at most 1000.

In calls to MyCalendar.book(start, end), start and end are integers in the range [0, 10^9].

----------------------

class MyCalendar {
    private TreeMap<Integer, Integer> map;
    public MyCalendar() {
        map = new TreeMap<>();
    }
    
    public boolean book(int start, int end) {
        if (map.containsKey(start)) return false;
        if ((null == map.lowerKey(start) || map.lowerEntry(start).getValue() <= start) &&
            (null == map.higherKey(start) || map.higherKey(start) >= end)) {
            
            map.put(start, end);
            return true;
        }
        
        return false;
    }
}

/**
 * Your MyCalendar object will be instantiated and called as such:
 * MyCalendar obj = new MyCalendar();
 * boolean param_1 = obj.book(start,end);
 */

716. Max Stack

716. Max Stack

Design a max stack that supports push, pop, top, peekMax and popMax.

1. push(x) -- Push element x onto stack.
2. pop() -- Remove the element on top of the stack and return it.
3. top() -- Get the element on the top.
4. peekMax() -- Retrieve the maximum element in the stack.
5. popMax() -- Retrieve the maximum element in the stack, and remove it. If you find more than one maximum elements, only remove the top-most one.

Example 1:

MaxStack stack = new MaxStack();
stack.push(5); 
stack.push(1);
stack.push(5);
stack.top(); -> 5
stack.popMax(); -> 5
stack.top(); -> 1
stack.peekMax(); -> 5
stack.pop(); -> 1
stack.top(); -> 5

Note:

1. -1e7 <= x <= 1e7
2. Number of operations won't exceed 10000.
3. The last four operations won't be called when stack is empty.

-------------------------
Solution #1
priority queue搞不定，只能treemap。 O(logN)

class MaxStack {
    
    class Node {
        public Node next;
        public Node pre;
        public int val;
        public Node(int val) {
            this.val = val;
            next = null;
            pre = null;
        }
    }
    
    class DoublyLinkedList {
        private Node head;
        private Node tail;
        
        public DoublyLinkedList() {
            head = new Node(0);
            tail = new Node(0);
            head.next = tail;
            tail.pre = head;
        }
        
        public void addToEnd(Node node) {
            node.pre = tail.pre;
            node.pre.next = node;
            node.next = tail;
            tail.pre = node;
        }
        
        public void remove(Node node) {
            node.pre.next = node.next;
            node.next.pre = node.pre;            
        }
        
        public int getLast() {
            return tail.pre.val;
        }
        
        public int removeLast() {
            int tmp = getLast();
            remove(tail.pre);
            
            return tmp;
        }
    }

    private DoublyLinkedList dll;
    private TreeMap<Integer, LinkedList<Node>> map;
    
    /** initialize your data structure here. */
    public MaxStack() {
        dll = new DoublyLinkedList();
        map = new TreeMap<>();
    }
    
    public void push(int x) {
        Node node = new Node(x);
        if (!map.containsKey(x)) {
            map.put(x, new LinkedList<Node>());
        }
        map.get(x).add(node);
        dll.addToEnd(node);
    }
    
    public int pop() {
        int last = dll.removeLast();
        map.get(last).pollLast();
        if (map.get(last).isEmpty()) {
            map.remove(last);
        }
        
        return last;
    }
    
    public int top() {
        return dll.getLast();
    }
    
    public int peekMax() {
        return map.lastKey();
    }
    
    public int popMax() {
        int max = map.lastKey();
        dll.remove(map.get(max).pollLast());
        
        if (map.get(max).isEmpty()) {
            map.remove(max);   
        }
        
        return max;
    }
}

/**
 * Your MaxStack object will be instantiated and called as such:
 * MaxStack obj = new MaxStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.peekMax();
 * int param_5 = obj.popMax();
 */

Solution #2, 2个stack，ref：https://leetcode.com/problems/max-stack/solution/