Java greedy interval selection: an exchange proof and a limited objective

Java 8+. This is a complete program using JDK classes.

State exactly what is optimized

A loading bay can host one job at a time, and every accepted job counts equally. Sort by finish time, then accept a job whose start is at least the previous accepted finish. Intervals here are half-open, so a job ending at time 3 permits another to start at time 3.

The exchange argument justifies the choice. Replace the first interval of an optimal answer with the earliest-finishing available interval. It finishes no later, so the remaining selected intervals still fit. Repeat the argument on the remaining time window.

That proof does not optimize profit, duration or urgency. Assigning different values to jobs produces a different problem, often requiring a weighted recurrence. It also assumes one bay and fixed intervals; multiple resources need a new scheduling model.

Working program

import java.util.Arrays;
import java.util.Comparator;
public class LoadingBayIntervals {
    static int maximumCount(int[][] input){
        int[][] jobs=new int[input.length][2];
        for(int i=0;i<input.length;i++){
            if(input[i]==null||input[i].length!=2||input[i][0]>=input[i][1])throw new IllegalArgumentException("Invalid interval");
            jobs[i]=input[i].clone();
        }
        Arrays.sort(jobs,Comparator.comparingInt(job->job[1]));
        int finish=Integer.MIN_VALUE,accepted=0;
        for(int[] job:jobs)if(job[0]>=finish){accepted++;finish=job[1];}
        return accepted;
    }
    public static void main(String[] args){
        System.out.println(maximumCount(new int[][]{{1,4},{3,5},{0,2},{5,7},{2,3}}));
        System.out.println(maximumCount(new int[0][2]));
    }
}

Output

4
0

Costs and boundaries

Sorting n intervals takes O(n log n) work; the acceptance scan takes O(n). The defensive copy uses O(n) storage and prevents the sort from reordering caller-owned rows. Sorting endpoints by subtraction can overflow, so the comparator compares integers directly.

Common Mistakes

• The objective is count, not weighted value.
• Half-open versus closed intervals changes the equality check.
• Earliest start does not have the same exchange argument as earliest finish.

Read next

Ordering policies, Weighted-state reasoning.

Continue with range and graph boundaries

Continue with Java weighted interval scheduling: end-time sort and predecessor DP.