Traffic Sensor Matching

# Traffic Sensor Matching ## Difficulty Medium ## Tags `array`, `two pointers`, `greedy` ## Problem Statement You are analyzing traffic on a two-lane road (Northbound and Southbound) equipped with two sensors, **A** and **B**. - **Sensor A** is located South and only detects cars traveling **North**. - **Sensor B** is located North and detects **both** Northbound and Southbound cars. When a car travels North, it triggers Sensor A at time `t1` and then Sensor B at time `t2` (where `t2 > t1`). When a car travels South, it triggers only Sensor B. Given sorted lists of timestamps from both sensors, determine the maximum number of Northbound cars that can be identified. A valid Northbound car is a pair of timestamps `(a, b)` such that: 1. `a` is from Sensor A events. 2. `b` is from Sensor B events. 3. `0 < b - a <= time_limit`. Each timestamp can belong to at most one car. ## Constraints - 1 ≤ A.length, B.length ≤ 10⁵ - 1 ≤ time_limit ≤ 10⁶ - Timestamps are non-negative integers and sorted in ascending order. - Timestamps are unique within a single sensor's list (simplification). ## Signatures ### Python ```python def count_northbound_cars(timestamps_A: List[int], timestamps_B: List[int], time_limit: int) -> int: pass ``` ### Java ```java public class Solution { public int count_northbound_cars(List<Integer> timestamps_A, List<Integer> timestamps_B, int time_limit) { return null; } } ``` ### Csharp ```csharp public class Solution { public int count_northbound_cars(IList<int> timestamps_A, IList<int> timestamps_B, int time_limit) { throw new NotImplementedException(); } } ``` ### Cpp ```cpp class Solution { public: int count_northbound_cars(vector<int> timestamps_A, vector<int> timestamps_B, int time_limit) { } }; ``` ### C ```c int count_northbound_cars(int* timestamps_A, int* timestamps_B, int time_limit) { } ``` ### Ruby ```ruby def count_northbound_cars(timestamps_A, timestamps_B, time_limit) end ``` ### Perl ```perl sub count_northbound_cars { my ($self, @args) = @_; } ``` ### Scala ```scala object Solution { def count_northbound_cars(timestamps_A: List[Int], timestamps_B: List[Int], time_limit: Int): Int = { } } ``` ### Haskell ```haskell count_northbound_cars :: ... -> ... count_northbound_cars args = undefined ``` ### Clojure ```clojure (defn count_northbound_cars [timestamps_A timestamps_B time_limit] ) ``` ### Scheme ```scheme (define (count_northbound_cars timestamps_A timestamps_B time_limit) ) ``` ## Examples ### Example 1 **Input:** ``` A = [10, 20, 30] B = [12, 15, 25, 35] time_limit = 5 ``` **Output:** ``` 3 ``` **Explanation:** - A=10 matches B=12 (diff 2) - A=20 matches B=25 (diff 5) - A=30 matches B=35 (diff 5) - Matches: (10, 12), (20, 25), (30, 35). Total 3. - B=15 is unmatched (likely Southbound). ### Example 2 **Input:** ``` A = [10] B = [20] time_limit = 5 ``` **Output:** ``` 0 ``` **Explanation:** 20 - 10 = 10, which is > time_limit. No match. ### Example 3 **Input:** ``` A = [1, 2, 3] B = [4, 5, 6] time_limit = 3 ``` **Output:** ``` 3 ``` **Explanation:** (1,4), (2,5), (3,6) all have diff 3. ## Hints 1. **Sorted Input**: Since inputs are sorted, use a **Two Pointer** approach. 2. **Greedy Strategy**: Try to match the earliest `A` timestamp with the earliest valid `B` timestamp. 3. If `B[j] <= A[i]`: B happened before or at A (impossible for Northbound), so B[j] is Southbound (or noise). Move B pointer. 4. If `B[j] - A[i] > time_limit`: A[i] is too old to match any future B (since B is sorted). Move A pointer (this A is unmatched/missed). 5. If `0 < B[j] - A[i] <= time_limit`: Valid match! Count it, and move both pointers.