A transaction schedule interleaves operations from several transactions. It is conflict-serializable when those operations have the same effect as some serial execution of the transactions.
Design a TransactionScheduleAnalyzer class:
TransactionScheduleAnalyzer() creates a stateless analyzer.boolean isSerializable(int[] transactionIds, String[] operations, String[] items) reports whether the schedule is conflict-serializable.int[] serialOrder(...) returns the lexicographically smallest valid serial transaction order, or an empty array when the schedule is not serializable.
The three arrays are aligned. Entry i is one operation by transactionIds[i], where operations[i] is "R" or "W" and items[i] is the accessed data item.
Two operations conflict when they:
- Belong to different transactions.
- Access the same item.
- Include at least one write.
For every conflicting pair, add a precedence edge from the earlier transaction to the later transaction. The schedule is serializable exactly when this graph is acyclic.
Example 1:
Input:
Output:
Explanation: Transaction 1 writes x before transaction 2 reads it, so the graph contains only 1 -> 2.
Example 2:
Input:
Output:
Explanation: The conflict on x requires 1 before 2, while the conflict on y requires 2 before 1. No serial order can satisfy both.
Constraints
1 <= transactionIds.length == operations.length == items.length <= 5001 <= transactionIds[i] <= 10^9operations[i] is "R" or "W".- Item names are non-empty lowercase strings.
- Every transaction ID appears in at least one operation.
- At most
100 total method calls are made.
Analyze Transaction Serializabilityhard