## Problem Given one candidate interval and a list of existing intervals, determine whether the candidate conflicts with any existing interval. All intervals use half-open semantics `[start, end)`: an interval ending at time `t` does not conflict with one starting at `t`. ### Function Contract Implement `hasIntervalConflict(candidate, intervals)` where every interval is `[start, end]` with `start < end`. ### Constraints & Assumptions - `0 <= len(intervals) <= 1,000,000`. - Endpoints are signed 64-bit integers. - Existing intervals may be unsorted and may overlap one another. - Return as soon as one conflict is found. ### Clarifying Questions to Ask - Are endpoints inclusive? Start is inclusive and end is exclusive. - Does touching at one endpoint count as conflict? No. - Are existing intervals sorted or disjoint? Neither is guaranteed. - Is input validation required? Inputs satisfy `start < end`. ```hint Negate non-overlap Two half-open intervals do not overlap when one ends at or before the other starts. The conflict predicate is the negation of that condition. ``` ### Examples ```text candidate = [4, 7] intervals = [[1, 3], [7, 9]] output = false candidate = [4, 7] intervals = [[1, 5], [8, 9]] output = true ``` ### Evaluation Focus - Uses the correct half-open overlap predicate. - Handles containment and equal-start cases without enumerating many special cases. - Avoids unnecessary sorting for a single query. - Runs in `O(n)` time and `O(1)` extra space. ### Extensions to Discuss 1. Which data structure supports many candidate queries against a fixed interval set? 2. How does the predicate change for closed intervals? 3. How would you return all conflicting interval indices?