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.
Problem: Task Management System (Level 1)
Implement a simple task management system that supports adding tasks and retrieving the list of “current tasks”.
Requirements
Add task: create a task and store it in the system. Get current tasks: print the tasks currently stored in the system (in the required output format). Task model (suggested)
Each task contains at least:
taskId: unique identifier (int or string) taskName: string startTime: integer endTime: integer I/O (abstract) The input is a sequence of commands (e.g., ADD_TASK ..., GET_TASKS). For each GET_TASKS, print the task list in the required format.
Constraints
Number of tasks: up to 1e4. Sample test ideas Add 1 task then list; output contains that task. Add multiple tasks then list; output contains all tasks. List with no tasks; output is empty. Task names with spaces/special chars; formatting is correct. Overlapping task times; Level 1 does not require conflict validation.
Function Description
Complete solveTaskManagementSystem. It has one parameter, String input, containing the full stdin payload. Return the stdout payload as an array of lines, without trailing newline characters.
Constraints
Use the limits and requirements stated in the prompt.
Example 1
Input:
input = "ADD_TASK 1 \"Email\" 0 5\nGET_TASKS"Output:
["Task(id=1,name=Email,start=0,end=5)"]Explanation: The returned string must match the expected standard output for the sample input.
解法
按行解析命令：ADD_TASK id "name" start end 用正则提取，存入按插入顺序的列表；GET_TASKS 时按格式打印每条记录。时间复杂度 O(N) 命令数。
import re
from typing import List
def solveTaskManagementSystem(input: str) -> List[str]:
tasks = []
out = []
for line in input.split('\n'):
if line.startswith('ADD_TASK'):
m = re.match(r'ADD_TASK\s+(\S+)\s+"([^"]*)"\s+(\d+)\s+(\d+)', line)
if m:
tasks.append((m.group(1), m.group(2), int(m.group(3)), int(m.group(4))))
elif line.strip() == 'GET_TASKS':
for tid, name, s, e in tasks:
out.append(f"Task(id={tid},name={name},start={s},end={e})")
return outclass Solution {
String[] solveTaskManagementSystem(String input) {
List<String[]> tasks = new ArrayList<>();
List<String> out = new ArrayList<>();
Pattern p = Pattern.compile("ADD_TASK\\s+(\\S+)\\s+\"([^\"]*)\"\\s+(\\d+)\\s+(\\d+)");
for (String line : input.split("\n")) {
if (line.startsWith("ADD_TASK")) {
Matcher m = p.matcher(line);
if (m.find()) tasks.add(new String[]{m.group(1), m.group(2), m.group(3), m.group(4)});
} else if (line.trim().equals("GET_TASKS")) {
for (String[] t : tasks) {
out.add("Task(id=" + t[0] + ",name=" + t[1] + ",start=" + t[2] + ",end=" + t[3] + ")");
}
}
}
return out.toArray(new String[0]);
}
}class Solution {
public:
vector<string> solveTaskManagementSystem(string input) {
vector<array<string, 4>> tasks;
vector<string> out;
regex pat("ADD_TASK\\s+(\\S+)\\s+\"([^\"]*)\"\\s+(\\d+)\\s+(\\d+)");
stringstream ss(input);
string line;
while (getline(ss, line)) {
smatch m;
if (regex_search(line, m, pat) && line.find("ADD_TASK") == 0) {
tasks.push_back({m[1].str(), m[2].str(), m[3].str(), m[4].str()});
} else if (line.find("GET_TASKS") != string::npos) {
for (auto& t : tasks) {
out.push_back("Task(id=" + t[0] + ",name=" + t[1] + ",start=" + t[2] + ",end=" + t[3] + ")");
}
}
}
return out;
}
};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.
Problem: User Quota Scheduling with Expiring Assignments (Level 3)
Implement a user/task scheduling system.
Requirements
Create user: each user has a quota meaning the maximum number of concurrent assignments allowed for that user. Assign a task: assign to a user a time interval [startTime, endTime) with a taskId.
Rules
Each assignment is active on the half-open interval [startTime, endTime). Once endTime is reached, the assignment expires and no longer counts toward the user’s concurrent quota. Example: existing assignment [4,10) no longer counts for any t ≥ 10. If adding a new assignment would make the number of concurrent active assignments exceed quota at any time, the assignment must be rejected.
Output
For each assignment attempt, output whether it succeeds (e.g., true/false or OK/FAIL per spec).
Constraints
Potentially large, but OA tests may be small; a straightforward approach may pass. Test ideas quota=1: add [4,10) ok; add [10,12) ok. quota=1: add [4,10) ok; add [9,12) reject. quota=2: adding a third overlapping interval should reject. Edge: zero-length intervals (per spec). Multiple users are independent.
Function Description
Complete solveUserQuotaScheduling. It has one parameter, String input, containing the full stdin payload. Return the stdout payload as an array of lines, without trailing newline characters.
Constraints
Use the limits and requirements stated in the prompt.
Example 1
Input:
input = "CREATE_USER u1 1\nASSIGN u1 1 4 10\nASSIGN u1 2 10 12"Output:
["OK", "OK"]Explanation: The returned string must match the expected standard output for the sample input.
解法
每用户维护 quota 和已接受的活跃区间列表。ASSIGN 请求时：先剔除过期区间(半开区间 end ≤ 新 start 的可以剔除？不行—要看任意时刻的并发数)。正确做法：把现有区间 + 新区间一起做扫描线(端点排序，开区间事件 +1，闭区间事件 -1)，若任意时刻并发数超过 quota 则拒绝，否则接受。时间复杂度 O(K log K)，K 为该用户已有区间数。
from typing import List
def solveUserQuotaScheduling(input: str) -> List[str]:
users = {} # uid -> (quota, [(s, e), ...])
out = []
for line in input.split('\n'):
parts = line.split()
if not parts:
continue
if parts[0] == 'CREATE_USER':
uid, q = parts[1], int(parts[2])
users[uid] = [q, []]
elif parts[0] == 'ASSIGN':
uid, tid, s, e = parts[1], parts[2], int(parts[3]), int(parts[4])
quota, intervals = users[uid]
events = []
for a, b in intervals + [(s, e)]:
events.append((a, 1))
events.append((b, -1))
events.sort(key=lambda x: (x[0], x[1]))
cur = peak = 0
for _, delta in events:
cur += delta
peak = max(peak, cur)
if peak <= quota:
intervals.append((s, e))
out.append("OK")
else:
out.append("FAIL")
return outclass Solution {
String[] solveUserQuotaScheduling(String input) {
Map<String, int[]> quotaMap = new HashMap<>();
Map<String, List<int[]>> intervalsMap = new HashMap<>();
List<String> out = new ArrayList<>();
for (String line : input.split("\n")) {
String[] parts = line.trim().split("\\s+");
if (parts.length == 0 || parts[0].isEmpty()) continue;
if (parts[0].equals("CREATE_USER")) {
quotaMap.put(parts[1], new int[]{Integer.parseInt(parts[2])});
intervalsMap.put(parts[1], new ArrayList<>());
} else if (parts[0].equals("ASSIGN")) {
String uid = parts[1];
int s = Integer.parseInt(parts[3]), e = Integer.parseInt(parts[4]);
int quota = quotaMap.get(uid)[0];
List<int[]> intervals = intervalsMap.get(uid);
List<int[]> events = new ArrayList<>();
for (int[] iv : intervals) { events.add(new int[]{iv[0], 1}); events.add(new int[]{iv[1], -1}); }
events.add(new int[]{s, 1}); events.add(new int[]{e, -1});
events.sort((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
int cur = 0, peak = 0;
for (int[] ev : events) { cur += ev[1]; peak = Math.max(peak, cur); }
if (peak <= quota) { intervals.add(new int[]{s, e}); out.add("OK"); }
else out.add("FAIL");
}
}
return out.toArray(new String[0]);
}
}class Solution {
public:
vector<string> solveUserQuotaScheduling(string input) {
unordered_map<string, int> quotaMap;
unordered_map<string, vector<pair<int,int>>> intervalsMap;
vector<string> out;
stringstream ss(input);
string line;
while (getline(ss, line)) {
stringstream ls(line);
vector<string> parts;
string tok;
while (ls >> tok) parts.push_back(tok);
if (parts.empty()) continue;
if (parts[0] == "CREATE_USER") {
quotaMap[parts[1]] = stoi(parts[2]);
intervalsMap[parts[1]] = {};
} else if (parts[0] == "ASSIGN") {
string uid = parts[1];
int s = stoi(parts[3]), e = stoi(parts[4]);
int quota = quotaMap[uid];
auto& intervals = intervalsMap[uid];
vector<pair<int,int>> events;
for (auto& iv : intervals) { events.push_back({iv.first, 1}); events.push_back({iv.second, -1}); }
events.push_back({s, 1}); events.push_back({e, -1});
sort(events.begin(), events.end(), [](auto& a, auto& b) {
return a.first != b.first ? a.first < b.first : a.second < b.second;
});
int cur = 0, peak = 0;
for (auto& ev : events) { cur += ev.second; peak = max(peak, cur); }
if (peak <= quota) { intervals.push_back({s, e}); out.push_back("OK"); }
else out.push_back("FAIL");
}
}
return out;
}
};