maxNonOverlappingIntervals function

List<IntervalSchedulingUtils> maxNonOverlappingIntervals(List<IntervalSchedulingUtils> intervals)

Returns a maximal set of non-overlapping intervals from intervals, chosen by earliest end time (greedy).

See IntervalSchedulingUtils for the interval type.

Implementation

List<IntervalSchedulingUtils> maxNonOverlappingIntervals(List<IntervalSchedulingUtils> intervals) {
  if (intervals.isEmpty) return <IntervalSchedulingUtils>[];
  final List<IntervalSchedulingUtils> sorted = List<IntervalSchedulingUtils>.of(intervals)
    ..sort((IntervalSchedulingUtils a, IntervalSchedulingUtils b) => a.end.compareTo(b.end));
  final IntervalSchedulingUtils? firstInterval = sorted.firstOrNull;
  if (firstInterval == null) return <IntervalSchedulingUtils>[];
  final List<IntervalSchedulingUtils> out = <IntervalSchedulingUtils>[firstInterval];
  for (int i = 1; i < sorted.length; i++) {
    final IntervalSchedulingUtils lastInterval = out.lastOrNull ?? firstInterval;
    if (sorted[i].start >= lastInterval.end) out.add(sorted[i]);
  }
  return out;
}