How do you compute the time covered by a set of intervals?

Reported as a worked example on a September 2021 Codility comment, without a formal statement. The reading below is Inferred from those examples and from a reply that described merging intervals and summing endpoint differences.

Problem (inferred). Given a list of half-open or duration intervals [start, end], return the length of their union, measuring each span as end - start.

The reported examples:

• [1, 4], [2, 4] → 3 (the union is [1, 4], length 3)
• [3, 6], [5, 9], [11, 15] → 10 (the union is [3, 9] of length 6 plus [11, 15] of length 4)

The report did not say whether ends are open or closed. Measuring length as end - start, and merging when the next start is less than or equal to the current end, is consistent with both examples. Touching intervals such as [1, 2] and [2, 3] then cover length 2. If an interviewer meant a count of inclusive integer points, the answers would be different; ask.

Inferred constraints: intervals may arrive unsorted and may nest; an empty list covers 0; use long if the coordinates can overflow int.

Approach. Sort by start, then merge: keep a running [start, end], extend end when the next interval overlaps or touches, and otherwise add end - start and start a new span. Time O(n log n) for the sort, then O(n). Extra space O(n) if you copy before sorting, or O(log n) if you sort in place. This is the same merge used by LeetCode 56, Merge Intervals, except you return a length rather than the merged list.

import java.util.*;

public class CoveredTime {
    static int coveredTime(int[][] intervals) {
        if (intervals == null || intervals.length == 0) return 0;
        int[][] a = Arrays.copyOf(intervals, intervals.length);
        Arrays.sort(a, Comparator.comparingInt(e -> e[0]));
        int total = 0;
        int start = a[0][0], end = a[0][1];
        for (int i = 1; i < a.length; i++) {
            if (a[i][0] <= end) {
                end = Math.max(end, a[i][1]);
            } else {
                total += end - start;
                start = a[i][0];
                end = a[i][1];
            }
        }
        total += end - start;
        return total;
    }

    public static void main(String[] args) {
        System.out.println(coveredTime(new int[][] {{1, 4}, {2, 4}}));                 // 3
        System.out.println(coveredTime(new int[][] {{3, 6}, {5, 9}, {11, 15}}));        // 10
        System.out.println(coveredTime(new int[][] {{11, 15}, {3, 6}, {5, 9}}));        // 10
        System.out.println(coveredTime(new int[][] {{1, 2}, {2, 3}}));                  // 2
    }
}

Verified with OpenJDK 21.0.13: it prints 3, 10, 10 and 2.

Edge cases and follow-ups. Unsorted input; nested intervals; a single interval; empty input; touching versus strictly overlapping ends; whether to return the merged intervals themselves (LeetCode 56) or only the covered length.