Problem · Design
User Quota Scheduling with Expiring Assignments
Complete the function below. The function receives the full standard input as a single string and must return the exact standard output lines for the described problem.
Implement a user/task scheduling system supporting the following commands, one per line:
CREATE_USER <userId> <quota>— Creates a user with the given string identifieruserIdand integerquota, which is the maximum number of concurrently active assignments allowed for that user at any single point in time. This command produces no output.ASSIGN <userId> <taskId> <startTime> <endTime>— Attempts to assign a task with integer identifiertaskIdto the useruserIdover the half-open time interval[startTime, endTime). OutputOKif the assignment is accepted, orFAILif it is rejected.
Assignment Rules:
- Each assignment is active during the half-open interval
[startTime, endTime). The assignment expires atendTimeand no longer counts toward the user's concurrent quota for any timet >= endTime. - If adding a new assignment would cause the number of concurrently active assignments for that user to exceed the user's quota at any point in time, the assignment must be rejected (
FAIL). - A zero-length interval where
startTime == endTimeis instantly expired and never overlaps with any other interval; such assignments always succeed. - Users are independent; assignments for different users do not interact.
Output: For each ASSIGN command, output exactly one line: OK if the assignment was accepted, or FAIL if it was rejected. CREATE_USER commands produce no output line.
Examples
01 · Example 1
input = "CREATE_USER u1 1\nASSIGN u1 1 4 10\nASSIGN u1 2 10 12" return = ["OK", "OK"]
CREATE_USER u1 1 creates user u1 with quota 1 (no output). ASSIGN u1 1 4 10 assigns taskId=1 to u1 over [4,10); no existing assignments, so it succeeds → OK. ASSIGN u1 2 10 12 assigns taskId=2 to u1 over [10,12); the previous assignment [4,10) has expired by time 10, so at no point in [10,12) does the active count exceed quota 1 → OK. CREATE_USER produces no output line, so only 2 output lines are returned.
Constraints
- All
userIdvalues are non-empty strings. quotais a positive integer.taskIdis a non-negative integer.startTimeandendTimeare non-negative integers withstartTime <= endTime.- Assignments use the half-open interval
[startTime, endTime); an assignment expires atendTimeand does not count toward quota at or after that time. - A zero-length interval (
startTime == endTime) never overlaps any interval and always succeeds. - Multiple users are independent; their quotas and assignments do not interact.
- Each
ASSIGNcommand must produce exactly one output line (OKorFAIL);CREATE_USERcommands produce no output.
More Circle problems
public String[] solveUserQuotaScheduling(String input) {
// write your code here
}
input"CREATE_USER u1 1\nASSIGN u1 1 4 10\nASSIGN u1 2 10 12"
expected["OK", "OK"]
sign in to submit