Filled with optimism, Hyunuk will host a conference about how great this new year will…
- User
Filled with optimism, Hyunuk will host a conference about how great this new year will be!
The conference will have n lectures. Hyunuk has two candidate venues a and b. For each of the n lectures, the speaker specified two time intervals [sa_i, ea_i] (sa_i ≤ ea_i) and [sb_i, eb_i] (sb_i ≤ eb_i). If the conference is situated in venue a, the lecture will be held from sa_i to ea_i, and if the conference is situated in venue b, the lecture will be held from sb_i to eb_i. Hyunuk will choose one of these venues and all lectures will be held at that venue.
Two lectures are said to overlap if they share any point in time in common. Formally, a lecture held in interval [x, y] overlaps with a lecture held in interval [u, v] if and only if max(x, u) ≤ min(y, v).
We say that a participant can attend a subset s of the lectures if the lectures in s do not pairwise overlap (i.e. no two lectures overlap). Note that the possibility of attending may depend on whether Hyunuk selected venue a or venue b to hold the conference.
A subset of lectures s is said to be venue-sensitive if, for one of the venues, the participant can attend s, but for the other venue, the participant cannot attend s.
A venue-sensitive set is problematic for a participant who is interested in attending the lectures in s because the participant cannot be sure whether the lecture times will overlap. Hyunuk will be happy if and only if there are no venue-sensitive sets. Determine whether Hyunuk will be happy. Input
The first line contains an integer n (1 ≤ n ≤ 100 000), the number of lectures held in the conference.
Each of the next n lines contains four integers sa_i, ea_i, sb_i, eb_i (1 ≤ sa_i, ea_i, sb_i, eb_i ≤ 10^9, sa_i ≤ ea_i, sb_i ≤ eb_i).
Output
Print "YES" if Hyunuk will be happy. Print "NO" otherwise.
You can print each letter in any case (upper or lower).
Examples
Input
2 1 2 3 6 3 4 7 8
Output
YES
Input
3 1 3 2 4 4 5 6 7 3 4 5 5
Output
NO
Input
6 1 5 2 9 2 4 5 8 3 6 7 11 7 10 12 16 8 11 13 17 9 12 14 18
Output
YES
Note
In second example, lecture set {1, 3} is venue-sensitive. Because participant can't attend this lectures in venue a, but can attend in venue b.
In first and third example, venue-sensitive set does not exist.
Assistant
We need to check if there exists any subset of lectures that is "venue-sensitive": i.e., can be attended in one venue but not the other. The participant can attend a subset if the intervals (in that venue) are pairwise non-overlapping. So for a set S, we compare the intervals in venue A (s_i^a, e_i^a) and in venue B (s_i^b, e_i^b). The condition is: in venue A, all intervals are pairwise non-overlapping; in venue B, at least one pair overlaps (or vice versa). Equivalent: The set S is "good" in one venue but not in the other.
We need to check if any such S exists. If none, output YES; else NO.
Observation: Since the property is about pairwise non-overlap, it's about the comparability of intervals. This is reminiscent of interval graph properties. Specifically, we have two families of intervals for the same set of items. We need to ensure that the set of intervals in A and B have the same "conflict graph"? Actually we need that for every subset S, the property of being pairwise non-overlapping (i.e., being an independent set in the conflict graph where edges denote overlap) is the same in both venues. That is, the conflict graphs (over same vertex set) must be identical in terms of independent sets? Not exactly identical graphs, because we need that a set S is independent in graph G_A iff it is independent in G_B. That means the two graphs have exactly the same independent sets. That is a strong condition: two graphs on same vertex set have the same family of independent sets. That means the complement graphs (clique covers) have the same family of cliques? Not exactly.
But note: A set S is pairwise non-overlapping means no two intervals intersect. So S is an independent set in the interval overlap graph. The condition that no S is venue-sensitive means that for every subset S, the property "S is independent in G_A" is equivalent to "S is independent in G_B". So the two graphs have identical independent set families. That is equivalent to saying that the edge sets of the two graphs are identical? Not necessarily: Could there be two different graphs that have same independent sets? Let's think. The independent sets are those subsets containing no edge. If there is an edge in G_A that is not in G_B, then the pair of vertices that are adjacent in G_A but not in G_B would be an independent set in G_B but not in G_A, hence a venue-sensitive set of size 2. Indeed, a set of two vertices: if they overlap in A but not in B, then S = {i,j} is attendable in B (since they don't overlap) but not attendable in A. So that would be a venue-sensitive set. Similarly if they overlap in B but not in A. So for n>=2, any discrepancy in pairwise overlap would give a venue-sensitive set of size 2. However, caution: Could there be a case where two intervals overlap in both venues? Then the set {i,j} is not attendable in either, so it's not venue-sensitive. So only when the overlap status differs for some pair.
Thus a necessary condition is: For every pair of lectures i,j, they must overlap in A iff they overlap in B. Because otherwise the pair itself is a venue-sensitive set. Is that sufficient? Not necessarily. Could there be a venue-sensitive set of size >2 even if all pairs have same overlap status? If for all pairs, overlap in A equals overlap in B, then the two conflict graphs are identical. Then obviously the independent sets are identical, so no venue-sensitive set. So condition is both necessary and sufficient: The existence of any venue-sensitive set is equivalent to there existing at least one pair with different overlap status. Because if all pairs have same overlap, then the graphs are identical, and independent sets are identical. If there is a pair with different overlap, that pair itself is a venue-sensitive set (provided one of them is overlapping and the other not). So we need to check: For all i<j, do we have overlap_A(i,j) = overlap_B(i,j)?
But wait: Could there be a scenario where a pair overlaps differently but the set {i,j} is not venue-sensitive because perhaps in the venue where they don't overlap, there is still some other condition? No, attendability for a set of two lectures is simply that they do not overlap. So if in venue A they overlap, then you cannot attend both; if in venue B they do not overlap, then you can attend both. So that is exactly a venue-sensitive set. So yes, any differing pair gives a size-2 venue-sensitive set. Thus the problem reduces to: Check if for all pairs i,j, the intervals overlap in A exactly when they overlap in B.
But n is up to 100k, so O(n^2) is impossible. Need smarter check.
We have two sets of intervals. For each i, interval A_i = [sa_i, ea_i], B_i = [sb_i, eb_i]. Need to ensure that for any two i,j: max(sa_i, sa_j) <= min(ea_i, ea_j) iff max(sb_i, sb_j) <= min(eb_i, eb_j).
This is a kind of "interval order consistency" condition. I recall a known problem from Codeforces: "Venue" or something about comparing two interval graphs. There is a known solution using segment tree sweep line and sorting events.
We can think: The condition is that the relative ordering of intervals is the same in both venues? Actually intervals overlapping is a relation that is not transitive. However, we can think in terms of the "interval order" for non-overlap: For intervals that do NOT overlap, they are either completely to the left or right. So overlapping is symmetric.
The condition that overlap status is the same for all pairs is a strong condition. Possibly it implies that the intervals in A and B are "order-isomorphic" in some sense.
We can try to derive necessary and sufficient conditions that can be checked efficiently.
Let’s denote the intervals as [l_i, r_i] for A and [L_i, R_i] for B.
Define for each i: the set of j that overlap with i in A should equal set of j that overlap with i in B. Equivalent to same neighbor sets in overlap graph.
But checking all pairs is heavy.
Observation: If two intervals do not overlap, one is entirely to the left of the other: i.e., r_i < l_j or r_j < l_i.
If they overlap, then neither r_i < l_j nor r_j < l_i.
Thus overlap status equivalence means: for any i,j, we have r_i < l_j iff R_i < L_j? Actually careful: They do not overlap if and only if r_i < l_j or r_j < l_i. So we need: (r_i < l_j or r_j < l_i) <=> (R_i < L_j or R_j < L_i). This is symmetric.
Alternatively, we can think of ordering points: Consider sorting intervals by their start times. Overlap condition can be characterized.
A typical approach: For each interval i, define its "dominance" relations: For intervals that are completely to the left, i.e., i ends before j starts: r_i < l_j. In that case, we must also have R_i < L_j. Conversely, if r_i >= l_j but intervals may still not overlap if r_j < l_i? Actually if r_i >= l_j and r_j >= l_i, then they overlap. So overlapping condition is equivalent to not (r_i < l_j) and not (r_j < l_i). So overlap iff l_j <= r_i and l_i <= r_j. So equivalence of overlaps is equivalent to equivalence of the condition: (l_j <= r_i and l_i <= r_j). That is a logical condition.
Simplify: The condition that for all i,j, (l_j <= r_i and l_i <= r_j) is equivalent to (L_j <= R_i and L_i <= R_j). This is a global condition.
Maybe we can transform the problem to checking if the mapping between intervals preserves the partial order defined by "i is before j" meaning r_i < l_j (i completely left of j). Indeed, define a relation i < j if interval i ends before j starts. This is a strict partial order (transitive). Then overlapping is the negation of comparability in this partial order? Actually if intervals are not overlapping, then either i < j or j < i. So non-overlap is equivalent to comparability in this partial order (i.e., one is before the other). Overlap means they are incomparable (neither i<j nor j<i). So the condition that overlap status is same means that the comparability relation defined by i<j based on ends before starts is the same for both venues. That is, for all i,j, we have r_i < l_j iff R_i < L_j. So that's a nice condition: the partial order of intervals by "being to the left" must be identical for the two families.
Thus we need to check whether the two sets of intervals induce the same order relation "i is completely to the left of j". This is similar to checking if two interval orders are the same. Interval order is defined by intervals: i < j iff r_i < l_j. So we need that for all i,j, r_i < l_j <=> R_i < L_j.
This is reminiscent of checking if two sequences of intervals are consistent in terms of ordering of endpoints. Maybe we can sort intervals by something and compare.
Consider sorting by l_i (start) and then r_i (end) perhaps. But the condition is global. There is known technique: we can construct a data structure to check for any violation: exist i,j such that r_i < l_j but R_i >= L_j (or vice versa). Also the symmetric case: r_i >= l_j but R_i < L_j. But careful: The condition r_i < l_j is a strict order; the equivalence must hold both ways. So we want to check if there exists a pair where r_i < l_j but not (R_i < L_j). That is, r_i < l_j and R_i >= L_j. That would be a violation (overlap status differs because in A they don't overlap (i before j), but in B they overlap or j before i? Actually if R_i >= L_j, then it's possible that they overlap, but also possible that R_i >= L_j but also R_j < L_i? Wait, if r_i < l_j, then i is before j in A. In B, if R_i >= L_j, then it is not true that i is before j (since R_i < L_j would be false). However, B might still have j before i? Could have R_j < L_i? But if R_i >= L_j, then at least one direction could be overlapping? Actually we need to check the pair: r_i < l_j (so in A, i before j, so they don't overlap). In B, if R_i >= L_j, it does not necessarily mean they overlap; they could be such that j before i (i.e., R_j < L_i). But in that case, in B they also don't overlap (since one before other). However, the condition for non-overlap in B is R_i < L_j or R_j < L_i. Since we have R_i >= L_j, we must check if R_j < L_i holds. If R_j < L_i, then they are non-overlapping in B as well (with j before i). But would that still be a violation? Because in A, the order is i before j. In B, the order is j before i. The overlap status is the same: both are non-overlapping. But is the pair considered as having same overlap status? Yes, they are non-overlap in both. So the condition we need is that (r_i < l_j) is equivalent to (R_i < L_j) OR (R_j < L_i)? Actually no: The equivalence of overlap status means: (overlap in A) iff (overlap in B). Overlap in A is false if either r_i < l_j or r_j < l_i. So non-overlap is union of two exclusive possibilities. In B, non-overlap is also union of R_i < L_j or R_j < L_i. So for the pair to have same overlap status, we need: (r_i < l_j or r_j < l_i) is equivalent to (R_i < L_j or R_j < L_i). That is more complex than just equivalence of the binary relation r_i < l_j. For example, if r_i < l_j and R_j < L_i, then in A they are non-overlap (since r_i < l_j), and in B they are also non-overlap (since R_j < L_i). So both non-overlap, okay. So violation occurs only when exactly one of the two disjunctions is true. That is, when (r_i < l_j or r_j < l_i) XOR (R_i < L_j or R_j < L_i) is true.
Thus we need to detect any pair where these conditions differ.
But earlier we argued that if the graphs differ, there exists a pair of vertices that are adjacent in one but not the other. But is that always true? In graph terms, edge exists if intervals overlap (i.e., they are not comparable by the "before" order). So if the overlap graphs are different, there exists a pair {i,j} where in one graph they are adjacent (overlap) and in the other they are not adjacent (non-overlap). That is exactly when in one venue they overlap, in the other they don't. So that's exactly the XOR condition above where one disjunction is false (overlap false -> non-overlap) and the other true (overlap). But could there be a scenario where the graphs are different but not due to a single edge difference? If graphs differ, there is at least one pair where edge presence differs. So yes, there will be a pair with overlap in one but not the other. So that pair would be a venue-sensitive set. So checking for any such pair is sufficient.
Thus the problem reduces to: Does there exist i≠j such that intervals i and j overlap in exactly one of the two venues? If yes, answer NO (unhappy). Else YES.
So we need to detect if there exists a pair (i,j) with:
( (sa_i <= ea_j? Actually careful: Overlap condition: intervals [l_i, r_i] and [l_j, r_j] overlap if l_i <= r_j and l_j <= r_i. ) So we need:
Overlap_A(i,j) XOR Overlap_B(i,j) = true.
Equivalently, Overlap_A(i,j) != Overlap_B(i,j).
So we need to detect any inconsistency.
Now we need efficient algorithm for n up to 100k.
This looks like a 2D problem. For each interval, we have two representations. Overlap condition can be expressed as: intervals overlap if neither is completely to the left of the other. The condition "i is completely left of j" is r_i < l_j. So overlap iff not (r_i < l_j) and not (r_j < l_i). So Overlap = !(r_i < l_j) && !(r_j < l_i). So Overlap_A(i,j) = !(ea_i < sa_j) && !(ea_j < sa_i). Overlap_B(i,j) = !(eb_i < sb_j) && !(eb_j < sb_i).
Thus Overlap_A != Overlap_B means either:
Case 1: Overlap_A true and Overlap_B false. That is: (ea_i >= sa_j and ea_j >= sa_i) but (eb_i < sb_j or eb_j < sb_i). Since Overlap_B false means at least one of the "completely left" conditions holds. So either eb_i < sb_j or eb_j < sb_i.
Case 2: Overlap_A false and Overlap_B true. That is: (ea_i < sa_j or ea_j < sa_i) but (eb_i >= sb_j and eb_j >= sb_i).
We need to check existence of any such pair.
We can try to find a pair where, say, in A they overlap but in B, i is left of j (eb_i < sb_j). That is: ea_i >= sa_j and ea_j >= sa_i (so intervals A intersect) and eb_i < sb_j. Symmetrically, could be eb_j < sb_i.
Or similarly, the other case.
Alternatively, we can check both directions.
We could treat intervals as points in a plane: For each interval i, we have a point (l_i, r_i) but that's not symmetric. Overlap condition is about comparisons between l and r of two intervals.
One common approach for such problems is to sort intervals by something and then use data structures to check for inconsistencies. Perhaps we can think in terms of "order of endpoints". For interval orders, the condition that two interval orders are identical is equivalent to the ordering of intervals by their start times and end times being consistent. Another perspective: For any two intervals i and j, we must have that the relative order of their endpoints is the same. More precisely, consider the four values: l_i, r_i, l_j, r_j. Overlap condition can be determined by comparing l_i vs r_j and l_j vs r_i. For the two venues, we have two sets: (l_i^A, r_i^A) and (l_i^B, r_i^B). The condition that Overlap_A equals Overlap_B for all pairs is equivalent to saying that for any i,j, the truth values of (l_i^A <= r_j^A) and (l_j^A <= r_i^A) are the same as those for B.
This is reminiscent of a problem "The same graph" for interval graphs; there is a known solution using sorting by l and checking with a segment tree for maximum r among intervals with l less than something. Let's think.
Maybe we can rephrase the condition in terms of a total order of endpoints. Since intervals are defined on the line, overlap depends on ordering of starts and ends. If we sort all intervals by their start in A, we can check for inconsistencies with B. There's known Codeforces problem "The Fair Nut and Rectangles" but not.
Let's try to derive necessary and sufficient condition that can be checked in O(n log n). Perhaps we can use the concept of "interval graph isomorphism" or "comparability of intervals".
Another angle: We can treat each lecture as a point in 2D: (sa_i, ea_i) and (sb_i, eb_i). The condition that there is no inconsistent pair might be equivalent to that the mapping from A intervals to B intervals is monotone in some sense. Perhaps we can sort intervals by sa_i, and then ensure some constraints on sb_i, eb_i.
Consider sorting by sa_i. For i < j in this order (i.e., sa_i <= sa_j), what are the possibilities for overlap? Since sa_i <= sa_j, overlap_A(i,j) is true if sa_j <= ea_i (i.e., sa_j <= ea_i). If sa_j > ea_i, then i is completely before j (non-overlap, i before j). So for i before j in sorted order by start, overlap_A(i,j) is determined by comparing sa_j with ea_i. Specifically, if sa_j <= ea_i => overlap; else non-overlap (i before j).
Now, if there is an inconsistency, we might detect it by scanning sorted by sa_i. For each i, consider all j with sa_j <= ea_i (i.e., that could overlap with i). Among those, we need that overlap_B(i,j) is also true. But also for those j with sa_j > ea_i (non-overlap in A), we need overlap_B false. However, note that overlap_B could be false in either direction: could be i before j or j before i. So for i and j where sa_j > ea_i (so A: i before j), we need that in B they are also non-overlap, but they could be either i before j (eb_i < sb_j) or j before i (eb_j < sb_i). That's not as simple.
But maybe we can use the concept of "maximum end" among intervals with start less than something. For a fixed i, consider all j with sa_j <= sa_i? Hmm.
Alternatively, we could think about the complement: we need to ensure that for any i,j, if r_i < l_j then either R_i < L_j or R_j < L_i? Actually we need equivalence of the disjunction. That's messy.
Maybe we can transform to a condition on the combined intervals: For each i, define a point in 4D? No.
Another approach: Instead of checking all pairs directly, we can use a sweep line algorithm that checks for violations of type "A overlaps but B does not" and "A does not overlap but B does". This is similar to checking if two interval graphs are equal, which can be done by verifying that the set of "conflicting pairs" is same. That can be reduced to verifying that the interval orders are the same.
Let's explore the "interval order" equivalence more thoroughly.
Define for each interval its "endpoint pair". An interval order is defined by the condition: i < j iff r_i < l_j. This is a strict partial order. Two families generate the same order relation if for all i,j, r_i < l_j iff R_i < L_j.
But as we argued, this is not exactly the condition we need because we only care about overlap (incomparability) equivalence. However, if the order relations coincide, then obviously overlap equivalence holds (since overlap = not comparable). But is the converse true? Could it happen that order relations differ but overlap equivalence still holds? Consider i and j such that in A: r_i < l_j (i before j), so they are comparable (i<j). In B, suppose they are also comparable but in the opposite order: R_j < L_i (j before i). Then in both venues they are non-overlapping (since one is before the other). Overlap equivalence holds because both are non-overlap. But the order relation "i before j" is not the same; in A we have i<j, in B we have j<i. But our original condition for graph equality is only about edge existence (overlap). In this scenario, there is no edge in either graph, so graphs are same. But do we have a pair with different overlap status? No. So the graphs can be identical even if the underlying order directions differ. So the condition r_i < l_j <=> R_i < L_j is stronger than needed; it's not necessary. Indeed, the pair i,j with i before j in A and j before i in B would still have both non-overlap, so they are not a problem. Therefore we cannot reduce to simply checking the same "before" relation; we must allow the direction to flip as long as they are still comparable (non-overlap) in both. So the condition is that the comparability relation (whether they are comparable, i.e., one is before the other) must be the same. That is, for all i,j, (r_i < l_j or r_j < l_i) iff (R_i < L_j or R_j < L_i). So it's about the existence of a total order of intervals along the line? Actually comparability means intervals are disjoint (non-overlapping). So we need that the disjointness relation is the same in both venues.
Thus we need that for any pair, either both overlapping or both disjoint.
So we need to ensure that the set of pairs that are intersecting (overlapping) is the same in both. This is exactly the edge sets of the two interval graphs.
Now, how to check efficiently if two interval graphs (on same vertex set) are identical? Given intervals for each vertex, we can compute the set of overlapping pairs for each venue. But that's O(n^2) in worst case. However, interval graphs are chordal and have structure; perhaps we can compute something like the "maximal cliques" or the "interval representation uniqueness"? There is a known concept of "interval graph isomorphism" but we want equality, not isomorphism.
We could attempt to find a witness pair where overlapping differs. So we need to detect if there exists i,j such that Overlap_A(i,j) != Overlap_B(i,j). That's a classic problem: given two sets of intervals, find if there exists a pair of intervals that intersect in one set but not the other. Since n is 100k, we might use sweep line with segment tree or priority queue.
Idea: For each pair of intervals, overlapping in A is determined by comparing their start and end. Overlap in B similarly. If we could sort intervals by start in A and then maintain something to detect if there is a j that overlaps with i in A but not in B. But B condition for that pair involves both intervals' B intervals.
Maybe we can consider mapping intervals to a combined coordinate system. Or treat the problem as checking if the permutation of intervals sorted by something is consistent.
Alternatively, think of building a graph where edges represent "must be same" or something.
Let's consider the complement: find any violation. There are two types of violation:
Type 1: Overlap_A true, Overlap_B false.
That means: intervals i and j intersect in A, but are disjoint in B. Disjoint in B means one is completely to the left of the other: either eb_i < sb_j or eb_j < sb_i.
So condition: (sa_i <= ea_j and sa_j <= ea_i) and (eb_i < sb_j or eb_j < sb_i).
Type 2: Overlap_A false, Overlap_B true: (sa_i > ea_j or sa_j > ea_i) and (sb_i <= eb_j and sb_j <= eb_i). Actually Overlap_B true means not (eb_i < sb_j) and not (eb_j < sb_i). So (eb_i >= sb_j and eb_j >= sb_i).
But note: Overlap_A false means either i before j (ea_i < sa_j) or j before i (ea_j < sa_i). So it's (ea_i < sa_j or ea_j < sa_i). And Overlap_B true: (eb_i >= sb_j and eb_j >= sb_i).
Now, can we detect these violations efficiently? Perhaps by sorting intervals by sa and using some data structure on sb, eb.
Consider type 1: Overlap in A but disjoint in B. Since overlapping in A implies that intervals' A intervals intersect. So they are not ordered by start-end. For overlapping intervals, we cannot rely on a linear order.
Maybe we can consider all pairs that overlap in A, and check if any of them are disjoint in B. Similarly, all pairs disjoint in A, check if any overlap in B. Since number of overlapping pairs could be O(n^2) in worst case (e.g., all intervals overlap), we cannot iterate over all such pairs.
We need a more clever method.
Observation: The condition "no venue-sensitive set" is equivalent to the two interval graphs being equal. Interval graphs have a well-known characterization: they are chordal and have a consecutive clique ordering. But checking equality may be done by comparing the maximal cliques or the interval representations after sorting by some order.
Another thought: Could it be that the condition reduces to checking that for each interval, the set of intervals that start before its end in A should be the same as those in B? Not exactly.
Let's try to think about the total order of events. Suppose we sort all 2n endpoints of A intervals: we have sa_i and ea_i. In an interval graph, overlapping intervals are those where one interval starts before the other ends. If we process events in order of sa (start), then for each interval i, all intervals j that have sa_j <= ea_i and also sa_i <= ea_j (which is automatically if we consider those with sa_j <= ea_i and also satisfy that ea_j >= sa_i) will overlap with i. But among those with sa_j <= ea_i, we need to ensure they also satisfy ea_j >= sa_i to overlap. So essentially, intervals that start before i ends and end after i starts.
That is: Overlap(i,j) if sa_j is in (-inf, ea_i] and ea_j is in [sa_i, +inf). So for fixed i, the set of j overlapping with i is those with sa_j <= ea_i and ea_j >= sa_i.
Similarly for B.
Now, we need that for all i, the set of j (j != i) such that these conditions hold in A is exactly the same as set in B? Actually not exactly: For a particular i, the set of j that overlap with i in A must equal the set in B? Because if there is a j that overlaps with i in A but not in B, then pair (i,j) is a violation (type 1). Conversely, if j overlaps with i in B but not in A, that's a violation (type 2). So indeed, for each i, the neighbor set in the overlap graph must be identical. Because if there is any difference, that pair gives a violation. So we need for all i, N_A(i) = N_B(i). So the two graphs are identical. So we can check for each i, the set of intervals overlapping with i in A equals that in B. However, sets could be large, but we might be able to compare them efficiently using some hashing or by checking consistency of ordering.
Now, note that the neighbor set for interval i in an interval graph can be described as: all intervals j whose start is <= ea_i and whose end >= sa_i. That's like a 2D range: (sa_j, ea_j) such that sa_j <= ea_i and ea_j >= sa_i. That's essentially the set of points in the plane that are not in the quadrant defined by sa_j > ea_i or ea_j < sa_i. But it's easier: The intervals that do NOT overlap with i are those with ea_j < sa_i (completely left) or sa_j > ea_i (completely right). So the neighbor set is the complement of those two ranges.
Thus N_A(i) = all j except those with ea_j < sa_i or sa_j > ea_i.
So N_A(i) = V \ (Left(i) ∪ Right(i)), where Left(i) = {j: ea_j < sa_i} (intervals ending before i starts) and Right(i) = {j: sa_j > ea_i} (intervals starting after i ends). Similarly for B.
Thus for N_A(i) = N_B(i), it's equivalent to Left_A(i) ∪ Right_A(i) = Left_B(i) ∪ Right_B(i). Since these are complements, it's equivalent to the condition that the set of intervals that are completely to the left of i in A equals the set completely to the left of i in B, and similarly for right? Not exactly: The union of left and right in A must equal union in B. That does not require individually left sets to be equal, because an interval that is left in A could be right in B, but as long as it's still in the union (i.e., non-neighbor), that's okay. Indeed, if j is left of i in A (ea_j < sa_i), and in B it is right of i (sb_j > eb_i?), wait careful: For B, to be non-neighbor, we need either eb_j < sb_i (left) or sb_j > eb_i (right). So j could be left in A and right in B, but still non-neighbor in both, so it's in union both sides. So it's allowed that the classification as left/right differs, as long as the overall set of non-neighbors is same. That matches earlier: direction can flip.
Thus we need for each i: {j | ea_j < sa_i or sa_j > ea_i} = {j | eb_j < sb_i or sb_j > eb_i}. That is the condition.
Now, this condition must hold for all i.
We need to check if there exists i such that these sets differ. Equivalent to existence of i and j such that j is in the union for A but not for B, or vice versa. That is exactly a violation pair.
So we need to detect any (i,j) where (ea_j < sa_i or sa_j > ea_i) XOR (eb_j < sb_i or sb_j > eb_i). This is the same as earlier.
Thus the problem remains.
Now, how to check this globally? Possibly we can transform into checking two conditions:
- For all i, the number of intervals with ea_j < sa_i must equal the number with eb_j < sb_i? Not exactly, because the right side also includes those with sb_j > eb_i, and the left sets may differ.
But maybe we can use a sweep line with Fenwick trees that track intervals in terms of both A and B. Since the condition involves both A and B parameters of i and j, we might try to check for violation of type 1 (overlap in A, non-overlap in B) by scanning over A intervals sorted by something and checking B constraints.
Let's try to design an algorithm to find a type 1 violation: ∃ i,j: A intervals intersect, but B intervals are disjoint. That is, (sa_i <= ea_j and sa_j <= ea_i) and (eb_i < sb_j or eb_j < sb_i).
We can try to find a pair such that A intervals intersect and eb_i < sb_j. Similarly with eb_j < sb_i.
Note that if A intervals intersect, then we have sa_i <= ea_j and sa_j <= ea_i. So there is some overlap region. That means max(sa_i, sa_j) <= min(ea_i, ea_j).
Now, if eb_i < sb_j, then in B, i ends before j starts, so i is left of j. So essentially, i and j are intersecting in A but i is left of j in B.
Symmetrically, eb_j < sb_i means j left of i in B.
So type 1 violation is: intervals intersect in A, but in B one is completely to the left of the other.
Similarly type 2 violation: intervals are disjoint in A (one left of other) but intersect in B.
Thus the problem is symmetric. So we can check for existence of any pair where A intersect, B disjoint. If none, and also none of the opposite, then answer YES. But we can reduce one to the other by swapping A and B? Actually if we check both, but perhaps if we find no violation of type 1 and also none of type 2, then fine. But we can just check both.
Maybe we can design a sweepline that processes intervals in order of sa (A start), and for each i, we consider intervals j that start before i's end (sa_j <= ea_i). Among those, we need to check if any has eb_j < sb_i or eb_i < sb_j? But both i and j are symmetric.
Alternatively, we can treat the condition as: There exists i,j such that:
max(sa_i, sa_j) <= min(ea_i, ea_j) (A intersect)
and
eb_i < sb_j (i left of j in B)
This is a kind of 4-dimensional problem: we need to find if there exist two points (i and j) satisfying:
sa_i <= ea_j, sa_j <= ea_i, and eb_i < sb_j.
We could try to fix ordering on one of the dimensions to simplify.
Note that the condition eb_i < sb_j suggests an ordering in B: i ends before j starts. So if we sort intervals by sb (B start), then for any j, intervals i with eb_i < sb_j are those that end before j's start. So if we process intervals in increasing sb, we can maintain a data structure of intervals that have eb < current sb. Among those intervals, we need to check if any of them intersect in A with the current interval j. So that gives a candidate violation of type 1 where i is left of j in B and A intersect.
Similarly, we also need to check the symmetric case where eb_j < sb_i, which would be covered when we process i as the later one.
Thus we can do:
- For each interval, we have (sa, ea) and (sb, eb).
- We want to find i, j such that:
- eb_i < sb_j
- A_i and A_j intersect (i.e., max(sa_i, sa_j) <= min(ea_i, ea_j))
If we find such a pair, answer NO.
Similarly, we also need to check for type 2: A disjoint, B intersect. But maybe if we also swap roles of A and B, type 2 becomes type 1 for the swapped venues. So we can just run the same check with A and B swapped (i.e., find i, j such that eb_i < sb_j and A intersect, but that's type 1; type 2 would be ea_i < sa_j and B intersect). So we can check both by running the algorithm twice: once looking for pairs where B has "i left of j" and A intersect, and once looking for pairs where A has "i left of j" and B intersect. Actually type 2 is: A disjoint (so either ea_i < sa_j or ea_j < sa_i) and B intersect. This is symmetric to type 1 with A and B swapped. So we can just run the same detection algorithm with the roles of A and B swapped. That is, look for i,j such that ea_i < sa_j and B intersect. So overall, we need to detect if there exists a pair satisfying (A intersect and B left) OR (B intersect and A left). So we can implement a function that, given two sets of intervals (X and Y) and a relation "left" from Y, checks if there exists a pair with X intersect and Y left. Then run it with X=A, Y=B, and also with X=B, Y=A.
Thus we focus on solving subproblem: Given n items, each with intervals (x_l, x_r) and (y_l, y_r), determine if there exists i≠j such that:
- x intervals intersect: max(x_l_i, x_l_j) <= min(x_r_i, x_r_j)
- and y_i is left of y_j: y_r_i < y_l_j (or the other direction? Actually we want i left of j in Y, i.e., y_r_i < y_l_j). That is one direction; we also need to consider the symmetric j left of i? But if we process all pairs with y_r_i < y_l_j, we cover cases where i is left of j. The symmetric case where j left of i would be captured when we swap i and j (i becomes the left one). Since our condition is "exists i,j with y_r_i < y_l_j" and x intersect, we will detect both because if there is a pair where y_r_j < y_l_i, then swapping indices, we have i'=j, j'=i, then y_r_i' < y_l_j' holds. So checking existence of i,j with y_r_i < y_l_j and x intersect is sufficient to capture any case where Y has one left of the other and X intersect. However, careful: In type 1, we need "eb_i < sb_j or eb_j < sb_i". That is exactly "exists ordering where one is left of the other". So checking for any unordered pair such that there exists an order with y_r_i < y_l_j will capture both possibilities. So we can just check for existence of i,j with y_r_i < y_l_j and x intersect.
Thus we need to detect existence of a pair (i,j) satisfying:
y_r_i < y_l_j (i left of j in Y)
and
max(x_l_i, x_l_j) <= min(x_r_i, x_r_j) (X intersect)
We'll design an algorithm for this.
We have up to 100k intervals. We need O(n log n) or similar.
We can sort intervals by y_l (the start in Y). Then for each interval j (in increasing y_l), we consider intervals i with y_r_i < y_l_j (i.e., those that end before j's start). Among those i, we need to know if any interval i exists such that its x interval intersects with x interval of j. So we need to check if there is an i in the set S = {i: y_r_i < y_l_j} such that x_i intersects x_j.
Condition for x_i and x_j to intersect: x_l_i <= x_r_j and x_l_j <= x_r_i. Equivalent to x_l_i <= x_r_j and x_r_i >= x_l_j.
Given j fixed, we need to query among i in S: does there exist i such that x_l_i <= x_r_j and x_r_i >= x_l_j?
That is a 2D range query: i must satisfy y_r_i < y_l_j (temporal condition from Y) and x_l_i <= x_r_j and x_r_i >= x_l_j.
We could treat x_l_i and x_r_i as points in a plane, and we need to check if there is a point (x_l_i, x_r_i) with x_l_i <= XR and x_r_i >= XL (where XR = x_r_j, XL = x_l_j). That's like a rectangle query: x_l_i in (-inf, XR] and x_r_i in [XL, +inf). Additionally, we have condition on y_r_i.
We can process intervals in order of y_l_j (i.e., j's Y start). As we move j, we maintain a data structure of intervals i that have y_r_i < current y_l_j (since they are eligible). We need to answer queries: does there exist an i in DS such that x_l_i <= XR_j and x_r_i >= XL_j?
We could invert condition: The existence of i such that x_l_i <= XR and x_r_i >= XL. This is equivalent to: max_{i in DS with x_l_i <= XR} (x_r_i) >= XL? Actually if we consider all i with x_l_i <= XR, we can take the maximum of x_r_i among them. If that maximum >= XL, then there exists an i satisfying both. So we can use a segment tree or Fenwick tree keyed by x_l_i, storing the maximum x_r_i for intervals with that x_l_i (or better, for a prefix of x_l). Since x_l_i can be up to 1e9, we need coordinate compression.
But note: DS only includes intervals that have been "activated" (i.e., y_r_i < current y_l_j). As we increase y_l_j, we can add intervals i to DS when their y_r_i becomes less than the current y_l? Actually we sort intervals by y_l_j and process in increasing order. We can also sort intervals by y_r_i to add them to DS. For each j in order of y_l_j, we need all i with y_r_i < y_l_j. So we can maintain a pointer over intervals sorted by y_r_i, and insert them into DS as we go. So DS will contain intervals with y_r_i < current_y_l.
Then for each j, query DS for existence of an interval intersecting x_j as described. If yes, we found a violation.
But careful: i and j must be distinct; we might accidentally consider i=j if j is also in DS? However, when we process j, DS contains intervals with y_r_i < y_l_j. Could j itself be in DS? For j, we haven't inserted it yet because we insert based on y_r. Typically we process intervals in order of y_l_j, and we insert intervals based on y_r_i sorted order. To avoid self-match, we could ensure that we insert i only when its y_r_i is < current y_l_j; but j itself might have y_r_j < y_l_j? That would mean its own y_r < y_l, which is impossible since y_l <= y_r for intervals (since y_l = sb, y_r = eb, and sb <= eb). Actually it's possible that sb = eb (zero-length interval). Then y_r = y_l. Condition y_r_i < y_l_j requires strict inequality. For j itself, we would need y_r_j < y_l_j, which can't hold because y_r_j >= y_l_j. So j cannot satisfy y_r_j < y_l_j. So j is not in DS. Good.
Thus algorithm for checking existence of (i,j) with Y_left (i left of j) and X_intersect:
- For each interval, we have (x_l, x_r) and (y_l, y_r).
- Sort intervals by y_l (Y start) ascending. We'll process each as j.
- Also, sort intervals by y_r (Y end) ascending. We'll maintain a data structure DS of intervals that have y_r < current_y_l. As we iterate through j in increasing y_l, we add to DS all intervals i whose y_r < y_l_j (from the y_r sorted list).
- DS should support queries: given (XL, XR) for j (x_l_j, x_r_j), check if there exists an interval i in DS such that x_l_i <= XR and x_r_i >= XL. Equivalent to: max_{i in DS, x_l_i <= XR} (x_r_i) >= XL.
- To answer this, we can maintain a segment tree (or Fenwick) over compressed x_l values. For each x_l value, we want to keep the maximum x_r among intervals with that x_l. Then we need prefix max up to XR (i.e., for all x_l <= XR). So we can query the maximum x_r over x_l in [min_x, XR]. If that max >= XL, then answer YES.
- However, we also need to handle updates: when inserting an interval i, we set at its x_l coordinate: update the value to max(current, x_r_i). Since multiple intervals may have same x_l, we keep the maximum x_r.
- Additionally, we might need to consider that x_l_i values can be large; compress all x_l from all intervals (both A and B depending on role). In this function, x_l are from X intervals, which could be sa or sb depending on context. So we compress accordingly.
But is this sufficient? The condition for intersection is x_l_i <= x_r_j and x_r_i >= x_l_j. Our query using max over x_l_i <= XR gives us the maximum x_r among those with x_l_i <= XR. If that maximum x_r >= XL, then there exists an i with x_l_i <= XR and x_r_i >= XL, which is exactly the intersection condition. However, we must also ensure that the i we found also satisfies x_l_i <= x_r_j (which is XR) and x_r_i >= x_l_j (XL). Yes, that matches.
But is it possible that the max x_r from prefix is from an interval that does not actually satisfy x_l_i <= XR? The prefix query ensures x_l_i <= XR, so condition holds. The max x_r may be from any such i. If that max is >= XL, then that i's x_r_i >= XL, so both conditions satisfied. So that i works. Conversely, if there exists such an i, then the max over prefix will be at least x_r_i >= XL, so condition holds. So query is correct.
Thus we can detect existence of a violating pair.
We must also consider the symmetric case where Y_left condition is y_r_j < y_l_i? But as argued, our process with sorting by y_l and querying DS of intervals with y_r < y_l_j will catch pairs where i is left of j. To catch pairs where j is left of i, we would also need to consider the reverse direction? Actually if there exists a pair where y_r_j < y_l_i (j left of i) and X intersect, then swapping labels i and j, we have i'=j, j'=i, and condition becomes y_r_i' < y_l_j' (since y_r_j < y_l_i becomes y_r_i' < y_l_j') and X intersect still holds. So that pair will be found when processing j' (the one with larger y_l) in our algorithm. Because our algorithm iterates over all j in increasing y_l, and includes all i with y_r < y_l_j. If the pair (i,j) has y_r_j < y_l_i, then note that y_l_i is larger than y_r_j. When we process j' = i (the one with larger y_l), the other interval (j) will have y_r_j < y_l_i, so it will be in DS at that time. And we will query with j'=i, and DS includes j, and check intersection. So indeed, processing all j in order of y_l will catch any unordered pair where one is left of the other in Y, regardless of which is left. So we don't need separate handling.
Thus a single pass (sort by y_l) suffices to detect any pair with Y_left and X_intersect.
However, there is nuance: The DS we maintain includes intervals i that have y_r_i < current y_l_j. For a pair (i,j) where y_r_i < y_l_j, our algorithm when processing j will have i in DS (if i's y_r < y_l_j). Good. For a pair where y_r_j < y_l_i, when processing i, j will be in DS. So both cases covered.
Now we also need to consider that X_intersect condition is symmetric; but our query with j and DS i checks intersection as defined. Since intersection is symmetric, it's fine.
Thus the algorithm for detection of type 1 (X intersect, Y left) is correct.
Now we need to run it twice: first with X = A intervals, Y = B intervals (to find A intersect and B left). Then with X = B intervals, Y = A intervals (to find B intersect and A left). If any detection returns true, answer NO. Else YES.
But wait: Are there any edge cases where overlapping in X and left in Y but our algorithm might miss because the intervals are equal? Overlap condition uses <= and >=; left condition uses strict inequality: y_r_i < y_l_j. That's correct for "completely left" (non-overlap) because if y_r_i = y_l_j, then intervals touch at a point? The problem defines overlap as sharing any point in time; if intervals are [l, r] and [u, v], they overlap if max(l,u) <= min(r,v). If they touch at a point, say r = u, then max(l,u) = u, min(r,v) = r = u, so they overlap (since they share the point u = r). So touching counts as overlap. So non-overlap requires r < u or v < l. So left condition is strict: r_i < l_j. So using strict is correct.
Now for our detection: For type 1 violation, we need Overlap_A true and (eb_i < sb_j or eb_j < sb_i). So we are looking for strict inequality. So y_r_i < y_l_j is correct.
Similarly for type 2, we need Overlap_B true and (ea_i < sa_j or ea_j < sa_i). So left condition uses strict.
Now we also need to ensure that the intersection condition (X intersect) uses <= and >= correctly. Overlap condition is max(x_l_i, x_l_j) <= min(x_r_i, x_r_j). This is equivalent to x_l_i <= x_r_j and x_l_j <= x_r_i. So our query condition x_l_i <= XR and x_r_i >= XL is exactly that, given we also ensure x_l_j <= x_r_i (the second condition). However, our query only checks existence of i with x_l_i <= XR and x_r_i >= XL. But note that we also need x_l_j <= x_r_i; we have x_r_i >= XL = x_l_j, so that's satisfied. The other condition x_l_i <= x_r_j is ensured by x_l_i <= XR = x_r_j. So indeed it's correct.
One more nuance: Intersection condition is symmetric, but our query only checks from perspective of i in DS and j current. However, for the pair (i,j) to be considered, we require both conditions; our query exactly checks that for the fixed j and some i. Since we check all j, we cover all unordered pairs where i is in DS when processing j. But could there be a pair where both i and j are in DS at the time we process j? That would happen if both have y_r < y_l_j. But then y_l_i could be less than y_l_j as well. For the pair to satisfy y_r_i < y_l_j, it's true. But also need y_r_j < y_l_i? That might not hold. However, we only need one direction to be true for the Y_left condition. Our algorithm uses y_r_i < y_l_j as the left condition. If both are in DS, then for the pair (i,j) where i and j both have y_r < y_l_j, it's possible that y_r_i < y_l_j holds (since i is in DS) and also y_r_j < y_l_j, but that doesn't guarantee y_r_j < y_l_i. However, we are checking the condition with i as left and j as right. If y_r_i < y_l_j holds, that's sufficient for Y_left. So even if both are in DS, the pair may be counted when j is the one with larger y_l? Let's examine: Suppose we have two intervals i and j such that y_r_i < y_l_j and also y_r_j < y_l_i? That would require both y_r_i < y_l_j and y_r_j < y_l_i. Since y_l_i <= y_r_i (by interval property), this would imply y_l_i <= y_r_i < y_l_j and y_l_j <= y_r_j < y_l_i, which is impossible unless strict contradictions. So it cannot happen that both y_r_i < y_l_j and y_r_j < y_l_i simultaneously. Because from first, y_l_j > y_r_i >= y_l_i, so y_l_j > y_l_i. From second, y_l_i > y_r_j >= y_l_j, so y_l_i > y_l_j, contradiction. So only one of the two directions can be true (or none). So for any unordered pair, at most one of y_r_i < y_l_j or y_r_j < y_l_i holds. So each violating pair will be captured exactly once when processing the interval with larger y_l (the right one). So algorithm is correct.
Now, we need to implement this efficiently.
But we must also consider that we are searching for existence of any such pair. So we can stop early if found.
Now, what about coordinate compression for x_l? x_l can be up to 1e9. We'll compress all x_l values from the X intervals (which are either sa_i or sb_i depending on run). For each run, we need to compress accordingly.
Implementation details:
We'll have arrays:
sa[1..n], ea[1..n], sb[1..n], eb[1..n].
Define a function check(X_l, X_r, Y_l, Y_r) that returns true if there exists i≠j such that X_i intersects X_j and Y_r_i < Y_l_j.
We'll implement as described:
- Create list of indices 0..n-1.
- For each i, store xl = X_l[i], xr = X_r[i], yl = Y_l[i], yr = Y_r[i].
- Sort indices by yl ascending.
- Also, create an array of pairs (yr, i) and sort by yr ascending.
- We'll maintain a Fenwick tree or segment tree over compressed xl values. But we need to support prefix max query and point update (max). Fenwick tree can support prefix max if we use max operation and updates only increase values. However, we may have multiple intervals with same xl; we need to set the value to max xr for that xl. Since we only insert intervals, we can update by taking max. That's fine.
But we need to map xl to compressed index. We'll compress all xl values from all intervals (maybe for current run). Since we may call check twice with different X, we can compress separately each time, but that's fine.
Now, the algorithm steps:
Initialize DS empty.
Sort the indices by yl: orderJ.
Sort the indices by yr: orderAdd. We'll have pointer p = 0 for orderAdd.
For each j in orderJ (increasing yl):
// Add intervals i with yr < yl_j to DS while p < n and yr[orderAdd[p]] < yl_j: i = orderAdd[p] // insert i into DS: update at position comp(xl[i]) with value xr[i] (take max) update(comp(xl[i]), xr[i]) p++ // Now DS contains all i with yr < yl_j (i.e., Y-left relative to j) // Query DS for existence of an interval intersecting X_j. // We need to know if there exists i in DS with xl_i <= xr_j and xr_i >= xl_j. // Query: max_xr = query_max(1, comp(xr_j)) // prefix up to xr_j (using compressed index of xr_j). Need to ensure we consider xl <= xr_j. But our compression is on xl, not on xr_j. So we need to find the largest compressed index such that the original xl value <= xr_j. Since xl values are compressed, we can binary search in the sorted list of unique xl values to find the rightmost index where xl <= xr_j. Then query prefix max over that range. // If max_xr >= xl_j, then we found a violating pair. // But careful: The DS includes i's with various xl. Some i may have xl > xr_j; they are not in prefix. So we query only up to that threshold. // If found, return true. // Also need to ensure we don't consider j itself in DS, but as argued, it's not because yr_j < yl_j can't happen (since yr_j >= yl_j). So safe.After loop, return false.
Complexities: O(n log n) per check.
But we need to also consider the case where there are multiple intervals with same values. Works fine.
Now, we need to also consider that the intersection condition in X might need to consider equality correctly: X intersect condition uses <= and >=. Our query uses xl_i <= xr_j and xr_i >= xl_j. That's correct.
Now, we need to double-check if this algorithm catches all pairs with X intersect and Y_left. Consider a pair (i,j) such that yr_i < yl_j and X intersect. Without loss, assume yr_i < yl_j. Then when we process j (the one with larger yl), i will have been added to DS (since yr_i < yl_j). At that time, we query DS for intersection with j. Our query checks if there exists any i in DS such that xl_i <= xr_j and xr_i >= xl_j. Since i satisfies that (by X intersect), the query will succeed. So yes.
Now, what about the case where there are multiple intervals in DS and the max_xr from prefix might come from an interval that does not have xr_i >= xl_j? But if there exists any interval i satisfying both conditions, then the max_xr among those with xl_i <= xr_j will be at least xr_i, and since xr_i >= xl_j, the max will be >= xl_j. So we will detect. If no such interval, the max will be < xl_j. So correct.
Now, we must ensure we handle coordinate compression correctly: For query prefix up to xr_j, we need to consider all xl_i <= xr_j. Since xl_i are coordinates, we can sort unique xl values and for a given xr_j, we find the largest index where xl <= xr_j via binary search (upper_bound). Then query segment tree over indices [1..pos].
Now, we need a segment tree or Fenwick tree that supports point update (set to max) and prefix max query. Fenwick tree (Binary Indexed Tree) can do prefix max if we use max operation and only increase values. Since we only insert intervals (not delete), and we only update each point once (when we add the interval), and we always take max, it's okay. However, note that multiple intervals may have the same xl; we need to keep the maximum xr for that xl. Since we process insertions in arbitrary order, we can update with max: tree[index] = max(tree[index], value). Fenwick tree for prefix max: update at position i with value v: while i <= N: BIT[i] = max(BIT[i], v); i += i&-i. Query prefix max up to i: res = 0; while i>0: res = max(res, BIT[i]); i -= i&-i. This works if values are non-negative. Here xr can be up to 1e9, but it's fine.
But note: BIT for prefix max works only for point updates that increase values; it's correct because we never decrease. Good.
Alternatively, we could use segment tree.
Now, we must also handle the case where xr_j might be less than the smallest xl in DS. Then prefix range is empty; we can skip query (or query returns -inf). We'll treat that as no match.
Now, after we implement check(A_l, A_r, B_l, B_r) (to find A intersect and B left) and also check(B_l, B_r, A_l, A_r) (to find B intersect and A left). If either returns true, answer NO. Else YES.
But is that sufficient? Let's test with examples.
Example 1:
n=2 1: [1,2] [3,6] 2: [3,4] [7,8]
Compute A: [1,2] and [3,4] -> they are disjoint? interval1 ends at 2, interval2 starts at 3, they touch at 3? Actually max(1,3)=3, min(2,4)=2, 3<=2 false, so they do not overlap (disjoint). Overlap_B: [3,6] and [7,8] -> 3-6 and 7-8 are disjoint (6<7). So both are disjoint, so no violation. So answer YES. Our check:
Check A intersect & B left: Are there i,j with A intersect and B left? A intervals are disjoint, so no. Check B intersect & A left: B intervals are disjoint, so no. So returns false, YES.
Example 2:
n=3 1: [1,3] [2,4] 2: [4,5] [6,7] 3: [3,4] [5,5]
Let's compute overlaps:
A: intervals: 1:1-3, 2:4-5, 3:3-4. Overlap_A: 1 and 2: 3<4? Actually 1-3 and 4-5: 3<4? They are disjoint? max(1,4)=4, min(3,5)=3 => 4<=3 false, so disjoint. 1 and 3: 1-3 and 3-4