Command Palette

Search for a command to run...

Hectal

Lesson 15.1 · Intervals

What Overlap Means

Two intervals overlap when each starts before the other ends. Decide whether touching endpoints count.

10 min

Think of it like this

Two meetings in the same room clash if one starts before the other finishes. A meeting ending at 10:00 and another starting at 10:00 may or may not clash: it depends on the rules of the room, and the problem statement decides.

1.The overlap test

[a, b] and [c, d] overlap exactly when a <= d && c <= b (closed intervals, touching counts). For half-open intervals [a, b) where touching doesn't count, use a < d && c < b.

It's easier to think about when they don't overlap: one ends before the other starts (b < c or d < a). Overlap is the opposite.

When the intervals are sorted by start, you only need to compare each interval with the last one kept: overlap is just current.start <= last.end.

Overlap.java
public class Main {
    static boolean overlap(int[] x, int[] y) { return x[0] <= y[1] && y[0] <= x[1]; }
    public static void main(String[] args) {
        System.out.println(overlap(new int[]{1, 3}, new int[]{2, 6}));    // true
        System.out.println(overlap(new int[]{1, 4}, new int[]{4, 5}));    // true: they touch at 4
        System.out.println(overlap(new int[]{1, 2}, new int[]{3, 4}));    // false
    }
}

Output

true
true
false

Remember

  • Overlap ⇔ each starts before (or when) the other ends.
  • Decide whether touching counts from the problem statement.
  • After sorting by start, compare only with the last kept interval.

Common mistakes

  • Checking only one direction of the overlap.
  • Mixing closed and half-open rules.