Interval Scheduling: Code Templates in 6 Languages

function activitySelection(intervals) {
    // Sorting by end time puts the earliest-finishing interval
    // first, which leaves the most room for everything after it.
    intervals.sort((a, b) => a.end - b.end);

    const selected = [];
    let lastEnd = -Infinity;

    for (const interval of intervals) {
        // Half-open semantics: an interval that starts exactly
        // when the last one ends does not conflict.
        if (interval.start >= lastEnd) {
            selected.push(interval);
            lastEnd = interval.end;
        }
    }

    return selected;
}

def activity_selection(intervals):
    # The interval that finishes earliest is always safe to pick,
    # because it leaves the most room for the rest.
    intervals.sort(key=lambda x: x[1])

    selected = []
    last_end = float("-inf")

    for start, end in intervals:
        # start >= last_end means the interval fits after the
        # previous pick without overlapping it.
        if start >= last_end:
            selected.append((start, end))
            last_end = end

    return selected

public List<int[]> activitySelection(int[][] intervals) {
    // Sorting by end time lets the greedy choice always see the
    // interval that finishes earliest.
    Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));

    List<int[]> selected = new ArrayList<>();
    int lastEnd = Integer.MIN_VALUE;

    for (int[] interval : intervals) {
        // start >= lastEnd means the interval starts at or after
        // the previous pick ends, so the two do not overlap.
        if (interval[0] >= lastEnd) {
            selected.add(interval);
            lastEnd = interval[1];
        }
    }

    return selected;
}

vector<vector<int>> activitySelection(vector<vector<int>>& intervals) {
    // The interval that ends earliest keeps the most room free,
    // so sorting by end time makes the greedy choice safe.
    sort(intervals.begin(), intervals.end(),
         [](const vector<int>& a, const vector<int>& b) {
             return a[1] < b[1];
         });

    vector<vector<int>> selected;
    int lastEnd = INT_MIN;

    for (const auto& interval : intervals) {
        // An interval starting at or after lastEnd does not
        // overlap the previous selection, so it can be added.
        if (interval[0] >= lastEnd) {
            selected.push_back(interval);
            lastEnd = interval[1];
        }
    }

    return selected;
}

func activitySelection(intervals [][]int) [][]int {
    // Sorting by end time guarantees the earliest-finishing
    // interval is considered first, which keeps the most room
    // for the intervals that come after it.
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][1] < intervals[j][1]
    })

    selected := make([][]int, 0)
    lastEnd := math.MinInt32

    for _, interval := range intervals {
        // A start at or after lastEnd means the interval fits
        // after the previous pick without overlapping.
        if interval[0] >= lastEnd {
            selected = append(selected, interval)
            lastEnd = interval[1]
        }
    }

    return selected
}

def activity_selection(intervals)
    # Sorting by end time puts the earliest-finishing interval
    # first, which leaves the most room for the rest of the day.
    intervals.sort_by! { |interval| interval[1] }

    selected = []
    last_end = -Float::INFINITY

    intervals.each do |start, finish|
        # start >= last_end means the interval begins at or after
        # the previous pick ends, so there is no overlap.
        if start >= last_end
            selected << [start, finish]
            last_end = finish
        end
    end

    selected
end

function merge(intervals) {
    if (intervals.length === 0) return [];

    // Sorting by start time means any overlap with a previous
    // interval always involves the last entry in the result.
    intervals.sort((a, b) => a.start - b.start);
    const merged = [intervals[0]];

    for (let i = 1; i < intervals.length; i++) {
        const last = merged[merged.length - 1];
        const current = intervals[i];

        if (current.start <= last.end) {
            // Overlap: widen the merged interval to cover both.
            last.end = Math.max(last.end, current.end);
        } else {
            // No overlap: the current interval starts a new block.
            merged.push(current);
        }
    }

    return merged;
}

def merge(intervals):
    if not intervals:
        return []

    # Sorting by start time means an interval can only overlap
    # the most recently merged one.
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]

    for start, end in intervals[1:]:
        last_start, last_end = merged[-1]

        if start <= last_end:
            # The current interval extends the previous one, so
            # widen the merged range instead of adding a new entry.
            merged[-1] = (last_start, max(last_end, end))
        else:
            merged.append((start, end))

    return merged

public int[][] merge(int[][] intervals) {
    if (intervals.length == 0) return new int[0][0];

    // Sorting by start time ensures each new interval can only
    // touch the most recently merged one.
    Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
    List<int[]> merged = new ArrayList<>();
    merged.add(intervals[0]);

    for (int i = 1; i < intervals.length; i++) {
        int[] last = merged.get(merged.size() - 1);
        int[] current = intervals[i];

        if (current[0] <= last[1]) {
            // Overlapping intervals merge into one, keeping the
            // later of the two end times.
            last[1] = Math.max(last[1], current[1]);
        } else {
            merged.add(current);
        }
    }

    return merged.toArray(new int[merged.size()][]);
}

vector<vector<int>> merge(vector<vector<int>>& intervals) {
    if (intervals.empty()) return {};

    // Sorting by start time means overlaps only ever touch the
    // last merged interval.
    sort(intervals.begin(), intervals.end());
    vector<vector<int>> merged;
    merged.push_back(intervals[0]);

    for (size_t i = 1; i < intervals.size(); i++) {
        vector<int>& last = merged.back();
        const vector<int>& current = intervals[i];

        if (current[0] <= last[1]) {
            // The current interval extends the merged one, so
            // widen the end instead of adding a new entry.
            last[1] = max(last[1], current[1]);
        } else {
            merged.push_back(current);
        }
    }

    return merged;
}

func merge(intervals [][]int) [][]int {
    if len(intervals) == 0 {
        return [][]int{}
    }

    // Sorting by start time limits overlap checks to the last
    // merged interval.
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][0] < intervals[j][0]
    })

    merged := [][]int{intervals[0]}

    for i := 1; i < len(intervals); i++ {
        last := merged[len(merged)-1]
        current := intervals[i]

        if current[0] <= last[1] {
            // Widen the merged interval to cover the overlap.
            last[1] = max(last[1], current[1])
            merged[len(merged)-1] = last
        } else {
            merged = append(merged, current)
        }
    }

    return merged
}

def merge(intervals)
    return [] if intervals.empty?

    # Sorting by start time means an interval can only overlap
    # the last merged interval.
    intervals.sort_by! { |interval| interval[0] }
    merged = [intervals[0]]

    intervals[1..].each do |start, finish|
        last_start, last_end = merged[-1]

        if start <= last_end
            # The interval extends the merged one, so only the
            # end needs updating.
            merged[-1] = [last_start, [last_end, finish].max]
        else
            merged << [start, finish]
        end
    end

    merged
end

function minMeetingRooms(intervals) {
    // Sorting starts and ends independently turns the problem
    // into merging two timelines, one for meetings beginning
    // and one for meetings ending.
    const starts = intervals.map(i => i.start).sort((a, b) => a - b);
    const ends = intervals.map(i => i.end).sort((a, b) => a - b);

    let rooms = 0;
    let endIdx = 0;

    for (const start of starts) {
        if (start < ends[endIdx]) {
            // A meeting starts before the earliest room frees
            // up, so a new room is needed.
            rooms++;
        } else {
            // The earliest-ending meeting is done, so its room
            // can be reused.
            endIdx++;
        }
    }

    return rooms;
}

def min_meeting_rooms(intervals):
    # Two sorted timelines. Every start is matched against the
    # earliest end to see whether a room is free.
    starts = sorted(start for start, _ in intervals)
    ends = sorted(end for _, end in intervals)

    rooms = 0
    end_idx = 0

    for start in starts:
        if start < ends[end_idx]:
            # No room is free yet, so open a new one.
            rooms += 1
        else:
            # The room that ends earliest is now free, reuse it.
            end_idx += 1

    return rooms

public int minMeetingRooms(int[][] intervals) {
    // Sorting starts and ends separately creates two timelines
    // that merge with two pointers.
    int[] starts = new int[intervals.length];
    int[] ends = new int[intervals.length];

    for (int i = 0; i < intervals.length; i++) {
        starts[i] = intervals[i][0];
        ends[i] = intervals[i][1];
    }

    Arrays.sort(starts);
    Arrays.sort(ends);

    int rooms = 0;
    int endIdx = 0;

    for (int start : starts) {
        if (start < ends[endIdx]) {
            // The meeting starts while every room is occupied.
            rooms++;
        } else {
            // The earliest-ending meeting has ended, reuse its room.
            endIdx++;
        }
    }

    return rooms;
}

int minMeetingRooms(vector<vector<int>>& intervals) {
    // Two sorted timelines for starts and ends, matched with
    // two pointers to count simultaneous meetings.
    vector<int> starts, ends;
    for (const auto& interval : intervals) {
        starts.push_back(interval[0]);
        ends.push_back(interval[1]);
    }

    sort(starts.begin(), starts.end());
    sort(ends.begin(), ends.end());

    int rooms = 0;
    size_t endIdx = 0;

    for (int start : starts) {
        if (start < ends[endIdx]) {
            // All current rooms are occupied, allocate a new one.
            rooms++;
        } else {
            // The earliest ending meeting freed its room.
            endIdx++;
        }
    }

    return rooms;
}

func minMeetingRooms(intervals [][]int) int {
    // Separate starts and ends into their own sorted timelines,
    // then walk both with two pointers.
    starts := make([]int, len(intervals))
    ends := make([]int, len(intervals))

    for i, interval := range intervals {
        starts[i] = interval[0]
        ends[i] = interval[1]
    }

    sort.Ints(starts)
    sort.Ints(ends)

    rooms := 0
    endIdx := 0

    for _, start := range starts {
        if start < ends[endIdx] {
            // No room is free when this meeting starts.
            rooms++
        } else {
            // The meeting that ends earliest has freed a room.
            endIdx++
        }
    }

    return rooms
}

def min_meeting_rooms(intervals)
    # Two independent sorted timelines are merged with pointers,
    # one for meetings starting and one for meetings ending.
    starts = intervals.map(&:first).sort
    ends = intervals.map(&:last).sort

    rooms = 0
    end_idx = 0

    starts.each do |start|
        if start < ends[end_idx]
            # All rooms are busy, so a new room is required.
            rooms += 1
        else
            # The earliest-ending meeting is done, reuse the room.
            end_idx += 1
        end
    end

    rooms
end

function weightedIntervalScheduling(intervals) {
    // intervals is an array of [start, end, value].
    // Sorting by end time lets each interval find its compatible
    // predecessors with binary search.
    intervals.sort((a, b) => a[1] - b[1]);
    const n = intervals.length;

    const ends = intervals.map(interval => interval[1]);
    // dp[i] is the best total value using only the first i intervals.
    const dp = new Array(n + 1).fill(0);

    // First index whose end time is greater than target.
    const bisectRight = (arr, target) => {
        let lo = 0, hi = arr.length;
        while (lo < hi) {
            const mid = (lo + hi) >> 1;
            if (arr[mid] <= target) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    };

    for (let i = 1; i <= n; i++) {
        const [start, , value] = intervals[i - 1];

        // Only intervals that finish at or before start can
        // precede this one in a valid schedule.
        let k = bisectRight(ends, start);
        if (k > i - 1) k = i - 1; // an interval cannot precede itself

        const take = value + dp[k];
        const skip = dp[i - 1];
        dp[i] = Math.max(take, skip);
    }

    return dp[n];
}

from bisect import bisect_right

def weighted_interval_scheduling(intervals):
    # intervals is a list of (start, end, value).
    # Sorting by end time means each interval depends only on
    # intervals that finish before it starts.
    intervals.sort(key=lambda x: x[1])
    n = len(intervals)

    starts = [s for s, _, _ in intervals]
    ends = [e for _, e, _ in intervals]
    values = [v for _, _, v in intervals]

    # dp[i] is the best total value using only the first i intervals.
    dp = [0] * (n + 1)

    for i in range(1, n + 1):
        # Count the intervals that finish at or before this one
        # starts. Those are the compatible predecessors.
        k = bisect_right(ends, starts[i - 1])
        if k > i - 1:
            k = i - 1  # an interval cannot precede itself

        take = values[i - 1] + dp[k]
        skip = dp[i - 1]
        dp[i] = max(take, skip)

    return dp[n]