← 返回 waymo 的题目列表Find Continuous Time Intervals Satisfying Two Timestamp-Based Signals
类型：online_judge
Problem: Return Continuous Time Intervals Satisfying Two Timestamp-Based Signals
You are given two timestamp-based boolean signals: A and B.
Each signal is represented by a list of events. Each event is a pair (timestamp, value):
timestamp is an integer time;
value is either 0 or 1;
events in each signal are sorted by strictly increasing timestamp;
after an event occurs, the signal keeps that value until the next event;
before the first event of a signal, its default value is 0.
Given a query time range [start, end), return all maximal continuous half-open intervals [l, r) within this range such that:
A(t) == 1 and B(t) == 1
If no such interval exists, output 0.
Input Format
n m
A_timestamp_1 A_value_1
...
A_timestamp_n A_value_n
B_timestamp_1 B_value_1
...
B_timestamp_m B_value_m
start end
Output Format
Print the number of valid intervals k on the first line.
Then print k lines, each containing one interval:
l r
Intervals must be printed in increasing time order.
Constraints
0 <= n, m <= 2 * 10^5
0 <= timestamp, start, end <= 10^9
start <= end
timestamps are strictly increasing within each signal
value is either 0 or 1
Example
Input:
3 3
1 1
5 0
10 1
2 1
6 0
8 1
0 12
Output:
2
2 5
10 12
Example
Input
3 3
1 1
5 0
10 1
2 1
6 0
8 1
0 12
Output
2
2 5
10 12