Interval modeling

A **closed** interval [a, b] contains both endpoints; an **open** interval (a, b) contains neither. Two closed intervals that merely touch, such as [1, 4] and [4, 7], share the single point 4, so they overlap. Two open intervals (1, 4) and (4, 7) share nothing.

Run the first two presets of the animation on the same data, 1-4 and 4-7. Under the closed definition they overlap and the shared part is the single point [4, 4]; under the half-open definition they do not. The data did not change, only the meaning of the endpoints, and the answer flipped.

Closed intervals suit integer or discrete data (days 3 through 5 inclusive, line numbers). Open intervals mostly appear in mathematics; programs almost never need them.

1static boolean overlapsClosed(int[] a, int[] b) {
2    return a[0] <= b[1] && b[0] <= a[1];      // touching endpoints share a point
3}
4
5static boolean overlapsOpen(int[] a, int[] b) {
6    return a[0] < b[1] && b[0] < a[1];        // touching endpoints share nothing
7}

1static boolean overlaps(int a1, int b1, int a2, int b2, int kind) {     // kind 0: closed, 1: half-open, 2: open
2    if (kind == 0) return a1 <= b2 && a2 <= b1;       // closed: sharing a single point counts as overlap
3    return a1 < b2 && a2 < b1;                        // half-open and open: touching ends do not overlap
4}

A **half-open** interval [a, b) contains a but not b. It is the convention of most programming: substring(from, to), Arrays.copyOfRange(a, from, to), List.subList(from, to) and for (int i = from; i < to; i++) are all half-open. Its advantages are exact: the length is b - a, an empty interval is a == b, adjacent intervals [1, 4) and [4, 7) tile without a gap or overlap, and splitting [a, c) at b gives [a, b) and [b, c) with no endpoint counted twice.

Meeting schedules are naturally half-open: a meeting from 9:00 to 10:00 and another from 10:00 to 11:00 may share a room. That is why the “Touching: half-open does not” preset reports no overlap, and why the meeting-room algorithms in this chapter treat an end as happening before a start at the same time.

1static void halfOpenInJava() {
2    String s = "abcdefgh";
3    String part = s.substring(2, 5);          // half-open [2, 5): characters at 2, 3 and 4
4    System.out.println(part);                 // cde
5    System.out.println(part.length() == 5 - 2);   // length is end - start
6    // adjacent half-open ranges tile exactly
7    System.out.println(s.substring(0, 2) + s.substring(2, 5) + s.substring(5, 8));   // abcdefgh
8}

1static boolean overlaps(int a1, int b1, int a2, int b2, int kind) {     // kind 0: closed, 1: half-open, 2: open
2    if (kind == 0) return a1 <= b2 && a2 <= b1;       // closed: sharing a single point counts as overlap
3    return a1 < b2 && a2 < b1;                        // half-open and open: touching ends do not overlap
4}

Two intervals relate in one of a few ways. They are **disjoint** when one ends before the other starts, they **touch** when one's end equals the other's start, they **partially overlap**, one can be **nested** inside the other, or they are **equal**. One formula covers every case: two intervals overlap exactly when max(starts) < min(ends) for half-open intervals, or max(starts) <= min(ends) for closed ones, and in that case the intersection is [max(starts), min(ends)].

The negation is easier to remember: two intervals are disjoint exactly when one ends before the other starts. The animation's “Nested” preset shows the shared part [3, 5] being the whole inner interval, and “Clear overlap” shows [4, 6].

1// half-open intersection; returns null when the intervals do not overlap
2static int[] intersect(int[] a, int[] b) {
3    int start = Math.max(a[0], b[0]);
4    int end = Math.min(a[1], b[1]);
5    return start < end ? new int[]{start, end} : null;
6}

1static boolean overlaps(int a1, int b1, int a2, int b2, int kind) {     // kind 0: closed, 1: half-open, 2: open
2    if (kind == 0) return a1 <= b2 && a2 <= b1;       // closed: sharing a single point counts as overlap
3    return a1 < b2 && a2 < b1;                        // half-open and open: touching ends do not overlap
4}

Real input is messy: endpoints may come reversed (start after end), empty intervals appear, and the same data may be given as inclusive ranges while the algorithm expects half-open. **Normalisation** converts every input into one clean convention before anything else runs: swap reversed endpoints (or reject them), convert inclusive [a, b] to half-open [a, b + 1), drop empty intervals, and optionally sort.

Do it at the boundary of your code, once, and write the rest of the program for half-open data only. Mixing conventions is where < and <= bugs come from.

1// inclusive [a, b] pairs in any order -> sorted, non-empty half-open [a, b+1) pairs
2static int[][] normalize(int[][] inclusive) {
3    List<int[]> out = new ArrayList<>();
4    for (int[] r : inclusive) {
5        int lo = Math.min(r[0], r[1]);
6        int hi = Math.max(r[0], r[1]);
7        out.add(new int[]{lo, hi + 1});                       // half-open: every integer range now has length >= 1
8    }
9    out.sort(Comparator.comparingInt(x -> x[0]));
10    return out.toArray(new int[0][]);
11}

Almost every interval algorithm starts by sorting, and the sort key follows from the question. **Sort by start** when you sweep left to right and build things up (merging, inserting, intersections). **Sort by end** when you want to keep the interval that frees the line soonest (activity selection, minimum arrows). **Sort the endpoints themselves** as separate events when you only need counts (maximum overlap).

A tie-breaker is needed when keys are equal. For merging, ties on start do not change the result. For event sorting, the order of an end and a start at the same time decides whether touching intervals overlap, and the next lesson group builds on exactly that point. When intervals have equal starts and you want the longest one first, sort by start ascending and end descending.

1// by start ascending; for equal starts, longer interval first
2static void sortByStartThenLongest(int[][] a) {
3    Arrays.sort(a, (x, y) -> x[0] != y[0] ? Integer.compare(x[0], y[0]) : Integer.compare(y[1], x[1]));
4}
5
6// by end ascending; for equal ends, later start first (the shorter interval)
7static void sortByEnd(int[][] a) {
8    Arrays.sort(a, (x, y) -> x[1] != y[1] ? Integer.compare(x[1], y[1]) : Integer.compare(y[0], x[0]));
9}

1public static List<int[]> merge(int[][] intervals) {
2    Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));   // sort by start
3    List<int[]> merged = new ArrayList<>();
4    for (int[] cur : intervals) {
5        int[] last = merged.isEmpty() ? null : merged.get(merged.size() - 1);
6        if (last != null && cur[0] <= last[1]) {
7            last[1] = Math.max(last[1], cur[1]);     // overlap: extend
8        } else {
9            merged.add(cur);                         // gap: start a new interval
10        }
11    }
12    return merged;
13}