Add Two Piecewise-Constant Time Series

Problem: Add Two Piecewise-Constant Time Series and Output Breakpoints You are given two sequences A and B, each strictly increasing by timestamp. Each element is a pair (t, v). Definition A pair (t, v) means: for the time segment ending at timestamp t, the series value is v. More explicitly, for [(t1,v1),(t2,v2),...,(tk,vk)], it represents a piecewise-constant function: value is v1 on (t0, t1] value is v2 on (t1, t2] ... value is vk on (t{k-1}, tk] where t0 is the (implicit) starting point before the first timestamp. Task Compute the pointwise sum of the two series over time, producing a new series C in the same breakpoint list format. Return C as an increasing list of (t, sum) where each (t, sum) indicates the summed value on the segment ending at t. Example Input: A = [(1,3), (3,1), (5,3), (6,4), (10,1)] B = [(2,3), (6,3), (11,2)] Output: [(1,6),(2,4),(3,4),(5,6),(6,7),(10,3),(11,2)] Constraints (suggested) 1 <= len(A), len(B) <= 2*10^5 timestamp is integer and strictly increasing within each list v is integer (may be 0 or negative) Target time complexity O(len(A)+len(B)) Tests (stdin/stdout convention) Assume 3 lines: A pairs list (JSON-like) B pairs list (JSON-like) expected C list (JSON-like) Example Input [(1,3), (3,1), (5,3), (6,4), (10,1)] [(2,3), (6,3), (11,2)] Output [(1, 6), (2, 4), (3, 4), (5, 6), (6, 7), (10, 3), (11, 2)]