1603. Line With Cuts
Design a ticket line at a busy counter where friends sometimes cut in beside each other. LineWithCuts() starts with an empty line of integer ids.
void join(int id)putsidat the back. It is only called with ids that are not currently in the line.boolean cutIn(int id, int ahead)putsiddirectly beforeaheadand returns true; it returns false, changing nothing, ifaheadis not in the line oridalready is.boolean leave(int id)removesidfrom anywhere in the line and returns true, or returns false if it is absent.int serve()removes and returns the id at the front, or -1 if the line is empty.
Keep every operation O(1) with a doubly linked list and a hash map from id to node.
Example 1
- Input:
- operations = ["LineWithCuts","join","join","join","cutIn","serve","serve","serve","serve","serve"]arguments = [[],[1],[2],[3],[9,3],[],[],[],[],[]]
- Output:
- [null,null,null,null,true,1,2,9,3,-1]
- Explanation:
After joins 1, 2, 3, id 9 cuts in before 3, so the line serves 1, 2, 9, 3 and then reports -1.
Example 2
- Input:
- operations = ["LineWithCuts","serve","leave","cutIn","join","cutIn","cutIn","cutIn","serve","serve","serve","serve"]arguments = [[],[],[4],[1,2],[5],[5,5],[6,5],[7,5],[],[],[],[]]
- Output:
- [null,-1,false,false,null,false,true,true,6,7,5,-1]
- Explanation:
Cuts fail when the target is absent or the id is already queued; each later cut goes directly before 5.
Constraints
0 ≤ id, ahead ≤ 109; join is only called with ids not in the line; at most 2000 calls in total.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Input
- Each case is an operation log.
operationsnames the class first and then each method call;argumentsholds the arguments for each, in the same order. Your answer is one list with a result per operation -nullfor the constructor and for methods that return nothing.
Expected complexity
- Time
- O(1) per call
- Space
- O(n)