Revolving Door

整数リクエストのリストが表示されます. requests[ i ] には [ time , direction ] が含まれており、時刻に人がドアに到着し、入室 ( 1 ) または外出 ( 0 ) したかったことを意味します.

ドアが 1 つしかなく、ドアを使用するのに 1 単位時間かかるとすると、競合を解決するための次のルールがあります.

ドアは in の位置から始まり、最後の人が使用した位置に設定されます.

所定の時間にドアに人が 1 人しかいない場合、その人はドアを使用できます.

入場希望者が2人以上の場合、先に入場した人が優先され、先に行った方角が優先されます.

1 時間単位で誰もドアを使用しない場合、最初の位置に戻ります.

各要素に [time, direction] が含まれているリストのソートされたリストを返します.これは、 time で人が出入りしたことを意味します.

制約
0 ≤ n ≤ 100,000 ここで、n は requests の長さです

例 1

入力

requests = [
    [1, 0],
    [2, 1],
    [5, 0],
    [5, 1],
    [2, 0]
]

出力

[
    [1, 0],
    [2, 0],
    [3, 1],
    [5, 1],
    [6, 0]
]

説明

ドアは in から始まります

時間 1 では、1 人しかいないので外出できます.ドアが外れます.
時間2で2人だけど、出る人が優先だから出る.
時間 3 では、入ろうとしている人が入室できます.
5の時点で2人いますが、入った方が優先なので出ていきます.
時間 6 で、最後の人が外出できます.

例 2

入力

requests = [
    [1, 0],
    [2, 0],
    [2, 1],
    [1, 1]
]

出力

[
    [1, 1],
    [2, 0],
    [3, 0],
    [4, 1]
]

説明

ドアは in から始まります

時間 1 には 2 人がいますが、入ってくる人が優先されます.
時間 2 では、時間 1 に来た他の人が外出できます.ドアが外れる
時間 3 では、2 人がいますが、外出する人が優先されます.
時間 4 で、最後の人が入ることができます

直感

時刻表を作成します.

操作を行う

ドアが入っている場合は、まず入りたい人を入れてから、ドアを別の方法に変えて、入りたい人を出させます

時系列と扉の状態に気をつけて(無操作で一単位時間経過後に変化するので)

実装

タイムテーブル

       for (int[] request : requests) {
            int time = request[0];
            LinkedList<Integer> operations = timeTable.getOrDefault(time, new LinkedList<>());
            operations.addLast(request[1]);
            timeTable.put(time, operations);
        }

何も操作せずに1単位時間後にドアを変更する

            if (time - lastTime >= 1) {
                lastOperation = 1;
            }

時間の複雑さ

O(n): リクエスト全体をループする必要があります

スペースの複雑さ

O(n): タイムテーブルと回答を保存する必要があります

解決

import java.util.*;

class Solution {
    public int[][] solve(int[][] requests) {
        int[][] ans = new int[requests.length][2];
        int index = 0;
        int lastTime = -1;
        int lastOperation = 1;

        TreeMap<Integer, LinkedList<Integer>> timeTable = new TreeMap<>();
        for (int[] request : requests) {
            int time = request[0];
            LinkedList<Integer> operations = timeTable.getOrDefault(time, new LinkedList<>());
            operations.addLast(request[1]);
            timeTable.put(time, operations);
        }

        for (int time : timeTable.keySet()) {
            if (time - lastTime >= 1) {
                lastOperation = 1;
            }
            LinkedList<Integer> operations = timeTable.get(time);
            int operationTime = index == 0 ? time : Math.max(time, ans[index - 1][0] + 1);
            while (operations.size() > 0) {
                if (operations.contains(lastOperation)) {
                    ans[index][0] = operationTime++;
                    ans[index][1] = lastOperation;
                    lastTime = operationTime;
                    index++;
                    operations.removeFirstOccurrence(lastOperation);
                } else {
                    lastOperation = lastOperation == 1 ? 0 : 1;
                }
            }
        }
        return ans;
    }
}