Multi-Exchange Feed Synchronization (Minimum Window Coverage)

Consolidated Market Data (SIP) feeds at Jane Street and HRT ingest market quotes arriving asynchronously from $K$ distinct electronic exchanges $\mathcal{E} = \{E_1, E_2, \dots, E_K\}$.

You are given a chronologically sorted list of incoming quote packets quotes, where each quote is a tuple (timestamp, exchange_id, price), and a set of target exchange identifiers target_exchanges.

To calibrate cross-market correlation and fair pricing, the matching engine must find the tightest time window $[t_{start}, t_{end}]$ that contains at least one quote from every exchange in target_exchanges.

Your Task

Implement min_sync_window(quotes: list[tuple[float, str, float]], target_exchanges: set[str]) -> tuple[float | None, float | None, float | None] that returns (min_duration, t_start, t_end) representing:

1. min_duration: The minimum elapsed time $(t_{end} - t_{start})$ containing all target exchanges (rounded to 6 decimal places).
2. t_start and t_end: The boundary timestamps of that optimal synchronization window. If no window contains all target exchanges, return (None, None, None).

Constraints

• $1 \le \text{len}(quotes) \le 10^5$
• $1 \le \text{len}(target\_exchanges) \le 100$
• Quotes are sorted in non-decreasing order of timestamps.

Examples

quotes = [
    (1.0, 'BATS', 100.0),
    (2.5, 'NASDAQ', 100.1),
    (4.0, 'ARCA', 100.2),
    (4.2, 'NASDAQ', 100.15),
    (4.5, 'BATS', 100.05)
]
target = {'NASDAQ', 'ARCA', 'BATS'}
# Window [1.0, 4.0] has duration 3.0.
# Window [4.0, 4.5] contains ARCA (4.0), NASDAQ (4.2), BATS (4.5) with duration 0.5!
# Output: (0.5, 4.0, 4.5)