FastPrep
Problem · Intervals

Interval Usage with Non-Overlapping Overrides

Learn this problem
● HardCrusoe logoCrusoeFULLTIMEONSITE INTERVIEW

Problem statement

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

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.

Clarified FastPrep contract

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

solveIntervalUsageWithOverrides(input: String) → String[]

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.

Examples

Example 1

input = "10\n2\n1 2 1\n4 10 1\n1\n2 4 0"return = ["1000111111"]

The returned string array must match the expected standard output lines for the sample input.

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.
drafts saved locally
public String[] solveIntervalUsageWithOverrides(String input) {
    // write your code here
}
input"10\n2\n1 2 1\n4 10 1\n1\n2 4 0"
expected["1000111111"]
checking account