Activity Selection and Interval Scheduling

Earliest finish maximizes the number of compatible intervals

Use half-open intervals [start,end) so one interval may begin exactly when another ends. Require positive lengths to keep the exercise's boundary rules simple.

Copy codedata class Interval(val start: Int, val end: Int)

fun schedule(intervals: List<Interval>): List<Interval> {
    require(intervals.all { it.start < it.end })
    val chosen = mutableListOf<Interval>()
    var lastEnd: Int? = null
    for (interval in intervals.sortedWith(compareBy<Interval> { it.end }.thenBy { it.start })) {
        if (lastEnd == null || interval.start >= lastEnd) {
            chosen.add(interval)
            lastEnd = interval.end
        }
    }
    return chosen
}

Sorting costs O(n log n); the scan costs O(n). Using a nullable boundary avoids assuming start times are nonnegative. Earliest start or shortest duration alone are not equivalent greedy rules.

Exercise

Test negative times, touching endpoints, nested intervals, and duplicate intervals. Compare schedule size with an exhaustive subset search for small inputs.

Check: weighted interval scheduling is a different problem and generally requires dynamic programming rather than this cardinality-only rule.

Further reading: Algorithm design