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.
You are given a timeline of days ([1..D]) and two kinds of interval events:
Usage intervals: indicate whether a resource is in-use during that period.
Override intervals: override the final state during that period. Override intervals do not overlap each other.
A day is in use by default if at least one usage interval with value 1 covers that day. Usage intervals with value 0 do not clear another usage interval; they simply contribute no usage. Override intervals are the only intervals that force the final state to their value, and override intervals never overlap each other.
Rules:
By default, a day's state is determined by the union/combination of usage intervals.
If a day falls within an override interval, the override value takes precedence over usage.
Implement an algorithm to output the final state for each day from 1 to D.
Input (stdin)
Line 1: integer D.
Line 2: integer U.
Next U lines: l r v describing a usage interval ([l,r]) (inclusive), with v in {0,1}.
Next line: integer O.
Next O lines: l r v describing an override interval ([l,r]) (inclusive), with v in {0,1}. Override intervals never overlap.
Output (stdout)
One line: a string of length D over {'0','1'}, where the i-th char is the final state on day i.
Complexity
Preferably better than day-by-day simulation; e.g. O((U+O) log (U+O) + D).
Example
See tests below.
Example
Input
10
2
1 2 1
4 10 1
1
2 4 0
Output
1000111111
Function Description
Complete solveIntervalUsageWithOverrides. 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
1 ≤ D- Usage intervals and override intervals are inclusive.
- Usage is the union of all covering value-1 usage intervals.
- Override intervals do not overlap and take precedence over usage.
Example 1
Input:
input = "10\n2\n1 2 1\n4 10 1\n1\n2 4 0"Output:
["1000111111"]Explanation: The returned string array must match the expected standard output lines for the sample input.
解法
用差分数组分别统计 usage 覆盖次数和 override(直接区间赋值)。先扫 usage 差分得到每天的 usage_count[i]，再让 override 区间覆盖结果。最终每天的状态：若被某个 override 覆盖则取其值，否则看 usage_count 是否 > 0。复杂度 O(D + U + O)，空间 O(D)。
from typing import List
def solve_interval_usage_with_overrides(input_str: str) -> List[str]:
lines = input_str.split("\n")
idx = 0
D = int(lines[idx]); idx += 1
U = int(lines[idx]); idx += 1
diff = [0] * (D + 2)
for _ in range(U):
l, r, v = map(int, lines[idx].split()); idx += 1
if v == 1:
diff[l] += 1
diff[r + 1] -= 1
O = int(lines[idx]); idx += 1
override = [-1] * (D + 2)
for _ in range(O):
l, r, v = map(int, lines[idx].split()); idx += 1
for i in range(l, r + 1):
override[i] = v
out = []
cur = 0
for i in range(1, D + 1):
cur += diff[i]
if override[i] != -1:
out.append("1" if override[i] == 1 else "0")
else:
out.append("1" if cur > 0 else "0")
return ["".join(out)]import java.util.*;
class Solution {
List<String> solveIntervalUsageWithOverrides(String input) {
String[] lines = input.split("\n");
int p = 0;
int D = Integer.parseInt(lines[p++].trim());
int U = Integer.parseInt(lines[p++].trim());
int[] diff = new int[D + 2];
for (int i = 0; i < U; i++) {
String[] s = lines[p++].trim().split(" ");
int l = Integer.parseInt(s[0]), r = Integer.parseInt(s[1]), v = Integer.parseInt(s[2]);
if (v == 1) { diff[l]++; diff[r + 1]--; }
}
int O = Integer.parseInt(lines[p++].trim());
int[] override = new int[D + 2];
Arrays.fill(override, -1);
for (int i = 0; i < O; i++) {
String[] s = lines[p++].trim().split(" ");
int l = Integer.parseInt(s[0]), r = Integer.parseInt(s[1]), v = Integer.parseInt(s[2]);
for (int j = l; j <= r; j++) override[j] = v;
}
StringBuilder sb = new StringBuilder();
int cur = 0;
for (int i = 1; i <= D; i++) {
cur += diff[i];
if (override[i] != -1) sb.append(override[i] == 1 ? '1' : '0');
else sb.append(cur > 0 ? '1' : '0');
}
return List.of(sb.toString());
}
}class Solution {
public:
vector<string> solveIntervalUsageWithOverrides(string input) {
vector<string> lines;
string cur;
for (char c : input) {
if (c == '\n') { lines.push_back(cur); cur.clear(); }
else cur += c;
}
if (!cur.empty()) lines.push_back(cur);
int p = 0;
int D = stoi(lines[p++]);
int U = stoi(lines[p++]);
vector<int> diff(D + 2, 0);
for (int i = 0; i < U; i++) {
int l, r, v;
sscanf(lines[p++].c_str(), "%d %d %d", &l, &r, &v);
if (v == 1) { diff[l]++; diff[r + 1]--; }
}
int O = stoi(lines[p++]);
vector<int> override_(D + 2, -1);
for (int i = 0; i < O; i++) {
int l, r, v;
sscanf(lines[p++].c_str(), "%d %d %d", &l, &r, &v);
for (int j = l; j <= r; j++) override_[j] = v;
}
string out;
int c = 0;
for (int i = 1; i <= D; i++) {
c += diff[i];
if (override_[i] != -1) out += (override_[i] == 1 ? '1' : '0');
else out += (c > 0 ? '1' : '0');
}
return {out};
}
};