MyCalendar 中重疊判定邏輯的解說

if (start < date.get(1) && end > date.get(0)) {
    return false;  // There's an overlap
}

New:      |-----|   
Existing:          |-----|

New:              |-----|
Existing:  |-----|

New:       |-------|
Existing:     |------|

New:         |---|
Existing:   |-------|

New:     |-----------|
Existing:   |-----|

Closed:      A = [1, 3]        B = [3, 7]
             |-----●           ●-------|         ● shared point 3  ->  OVERLAP

Half-open:   A = [1, 3)        B = [3, 7)
             |-----○           ●-------|         ○ excluded        ->  NO OVERLAP

closed     [a0, a1] ∩ [b0, b1] ≠ ∅   <=>   a0 <= b1 && b0 <= a1
half-open  [a0, a1) ∩ [b0, b1) ≠ ∅   <=>   a0 <  b1 && b0 <  a1

intersection      = [ max(a0, b0),  min(a1, b1) ]        # valid iff the overlap test passes
overlap length    = max(0, min(a1, b1) - max(a0, b0))    # continuous / half-open measure
overlap int count = max(0, min(a1, b1) - max(a0, b0) + 1) # closed, counting integer points
union (bounding)  = [ min(a0, b0),  max(a1, b1) ]        # a TRUE union only if they overlap/touch
gap (if disjoint) = max(0, max(a0, b0) - min(a1, b1))

// java
// IDEA: canonical overlap / intersection / union predicates for 1D ranges.
//       Closed    [a0, a1] -> both ends INCLUDED, so "touching" (a1 == b0) IS an overlap
//       Half-open [a0, a1) -> end EXCLUDED,       so "touching" (a1 == b0) is NOT an overlap
public class RangeOps {

    // time = O(1), space = O(1)
    // closed [a0, a1] vs [b0, b1]  -> touching endpoints count as overlap
    static boolean overlapClosed(int a0, int a1, int b0, int b1) {
        return a0 <= b1 && b0 <= a1;
    }

    // time = O(1), space = O(1)
    // half-open [a0, a1) vs [b0, b1)  -> touching endpoints are NOT an overlap
    static boolean overlapHalfOpen(int a0, int a1, int b0, int b1) {
        return a0 < b1 && b0 < a1;
    }

    // time = O(1), space = O(1)
    // intersection range; meaningful only when the matching overlap test above is true
    static int[] intersection(int a0, int a1, int b0, int b1) {
        return new int[] { Math.max(a0, b0), Math.min(a1, b1) };
    }

    // time = O(1), space = O(1)
    // overlap MEASURE for half-open / continuous ranges (0 when disjoint or only touching)
    static int overlapLength(int a0, int a1, int b0, int b1) {
        return Math.max(0, Math.min(a1, b1) - Math.max(a0, b0));
    }

    // time = O(1), space = O(1)
    // overlap COUNT of integer points for closed ranges (note the "+ 1")
    static int overlapCountClosed(int a0, int a1, int b0, int b1) {
        return Math.max(0, Math.min(a1, b1) - Math.max(a0, b0) + 1);
    }

    // time = O(1), space = O(1)
    // union bounding range; a true union only when the two ranges overlap or touch
    static int[] union(int a0, int a1, int b0, int b1) {
        return new int[] { Math.min(a0, b0), Math.max(a1, b1) };
    }

    // time = O(1), space = O(1)
    // gap between two disjoint ranges (0 when they overlap or touch)
    static int gap(int a0, int a1, int b0, int b1) {
        return Math.max(0, Math.max(a0, b0) - Math.min(a1, b1));
    }
}

# python
# IDEA: canonical overlap / intersection / union predicates for 1D ranges.
#       Closed    [a0, a1] -> both ends INCLUDED, so "touching" (a1 == b0) IS an overlap
#       Half-open [a0, a1) -> end EXCLUDED,       so "touching" (a1 == b0) is NOT an overlap

# time = O(1), space = O(1)
def overlap_closed(a0, a1, b0, b1):
    return a0 <= b1 and b0 <= a1

# time = O(1), space = O(1)
def overlap_half_open(a0, a1, b0, b1):
    return a0 < b1 and b0 < a1

# time = O(1), space = O(1)
# meaningful only when the matching overlap test above is true
def intersection(a0, a1, b0, b1):
    return (max(a0, b0), min(a1, b1))

# time = O(1), space = O(1)
# continuous / half-open measure (0 when disjoint or only touching)
def overlap_length(a0, a1, b0, b1):
    return max(0, min(a1, b1) - max(a0, b0))

# time = O(1), space = O(1)
# closed ranges: number of shared integer points (note the "+ 1")
def overlap_count_closed(a0, a1, b0, b1):
    return max(0, min(a1, b1) - max(a0, b0) + 1)

# time = O(1), space = O(1)
# a TRUE union only when the two ranges overlap or touch
def union(a0, a1, b0, b1):
    return (min(a0, b0), max(a1, b1))

# time = O(1), space = O(1)
def gap(a0, a1, b0, b1):
    return max(0, max(a0, b0) - min(a1, b1))

// java
// IDEA: 2D overlap = AND of two independent 1D tests, one per axis.
//       rect = [x1, y1, x2, y2] (bottom-left, top-right), half-open on both axes.

// time = O(1), space = O(1)
static boolean rectOverlap(int[] r, int[] s) {
    return r[0] < s[2] && s[0] < r[2]      // x-ranges overlap
        && r[1] < s[3] && s[1] < r[3];     // y-ranges overlap
}

// time = O(1), space = O(1)
// intersection area; 0 when the rectangles only touch along an edge or a corner
static long rectOverlapArea(int[] r, int[] s) {
    long w = Math.max(0, Math.min(r[2], s[2]) - Math.max(r[0], s[0]));
    long h = Math.max(0, Math.min(r[3], s[3]) - Math.max(r[1], s[1]));
    return w * h;
}

# python
# IDEA: 2D overlap = AND of two independent 1D tests, one per axis.
#       rect = (x1, y1, x2, y2) (bottom-left, top-right), half-open on both axes.

# time = O(1), space = O(1)
def rect_overlap(r, s):
    return r[0] < s[2] and s[0] < r[2] \
       and r[1] < s[3] and s[1] < r[3]

# time = O(1), space = O(1)
# 0 when the rectangles only touch along an edge or a corner
def rect_overlap_area(r, s):
    w = max(0, min(r[2], s[2]) - max(r[0], s[0]))
    h = max(0, min(r[3], s[3]) - max(r[1], s[1]))
    return w * h