Coding Patterns
Interval Scheduling
Code Templates

Code Templates

Master interval scheduling patterns with these battle-tested code templates. Each template includes implementations in JavaScript, Python, Java, C++, Go, and Ruby with detailed explanations.

The “Main” Template: Activity Selection (Earliest Finish Time)

Problem: Select maximum number of non-overlapping intervals, choosing earliest finishing intervals first.

This template directly solves problems like Meeting Rooms and Non-overlapping Intervals.

function activitySelection(intervals) {
    // Sort by finish time
    intervals.sort((a, b) => a.end - b.end);

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

    for (const interval of intervals) {
        if (interval.start >= lastEnd) {
            result.push(interval);
            lastEnd = interval.end;
        }
    }

    return result;
}
def activity_selection(intervals):
    # Sort by finish time
    intervals.sort(key=lambda x: x[1])

    result = []
    last_end = float('-inf')

    for interval in intervals:
        if interval[0] >= last_end:
            result.append(interval)
            last_end = interval[1]

    return result
public class Solution {
    public List<int[]> activitySelection(int[][] intervals) {
        // Sort by finish time
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[1]));

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

        for (int[] interval : intervals) {
            if (interval[0] >= lastEnd) {
                result.add(interval);
                lastEnd = interval[1];
            }
        }

        return result;
    }
}
vector<vector<int>> activitySelection(vector<vector<int>>& intervals) {
    // Sort by finish time
    sort(intervals.begin(), intervals.end(),
         [](const vector<int>& a, const vector<int>& b) {
             return a[1] < b[1];
         });

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

    for (const auto& interval : intervals) {
        if (interval[0] >= lastEnd) {
            result.push_back(interval);
            lastEnd = interval[1];
        }
    }

    return result;
}
func activitySelection(intervals [][]int) [][]int {
    // Sort by finish time
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][1] < intervals[j][1]
    })

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

    for _, interval := range intervals {
        if interval[0] >= lastEnd {
            result = append(result, interval)
            lastEnd = interval[1]
        }
    }

    return result
}
def activity_selection(intervals)
    # Sort by finish time
    intervals.sort! { |a, b| a[1] <=> b[1] }

    result = []
    last_end = -Float::INFINITY

    intervals.each do |interval|
        if interval[0] >= last_end
            result << interval
            last_end = interval[1]
        end
    end

    result
end

Code Breakdown

Key Variables

  • lastEnd: Tracks the end time of the last selected interval
  • result: Stores the selected non-overlapping intervals
  • intervals.sort(): Critical sorting by end time for greedy selection

Visual Algorithm Flow 

Input: [1,4], [2,5], [6,8], [7,9]

Step 1: Sort by end time
Sorted: [1,4], [2,5], [6,8], [7,9]

Step 2: Greedy selection
lastEnd = -∞

Process [1,4]: 1 >= -∞ ✓ → Select [1,4], lastEnd = 4
Process [2,5]: 2 < 4 ✗ → Skip [2,5]
Process [6,8]: 6 >= 4 ✓ → Select [6,8], lastEnd = 8
Process [7,9]: 7 < 8 ✗ → Skip [7,9]

Result: [1,4], [6,8]

Critical Sections

  1. Initialization: Set lastEnd to negative infinity to accept first interval
  2. Expansion: Check if current interval can be added without overlap
  3. Contraction: Update lastEnd when interval is selected

Variations

Merge Intervals

For problems requiring interval merging:

Input: [1,3], [2,6], [8,10], [15,18]

Step 1: Sort by start time
Sorted: [1,3], [2,6], [8,10], [15,18]

Step 2: Merge overlapping intervals
result = [[1,3]]

Process [2,6]: 2 <= 3 ✓ → Merge → result = [[1,6]]
Process [8,10]: 8 > 6 ✗ → Add new → result = [[1,6], [8,10]]
Process [15,18]: 15 > 10 ✗ → Add new → result = [[1,6], [8,10], [15,18]]

Result: [1,6], [8,10], [15,18]
function merge(intervals) {
    if (intervals.length === 0) return [];

    intervals.sort((a, b) => a.start - b.start);
    const result = [intervals[0]];

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

        if (current.end >= next.start) {
            current.end = Math.max(current.end, next.end);
        } else {
            result.push(next);
        }
    }

    return result;
}
def merge(intervals):
    if not intervals:
        return []

    intervals.sort(key=lambda x: x[0])
    result = [intervals[0]]

    for i in range(1, len(intervals)):
        current = result[-1]
        next_interval = intervals[i]

        if current[1] >= next_interval[0]:
            current[1] = max(current[1], next_interval[1])
        else:
            result.append(next_interval)

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

    Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
    List<int[]> result = new ArrayList<>();
    result.add(intervals[0]);

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

        if (current[1] >= next[0]) {
            current[1] = Math.max(current[1], next[1]);
        } else {
            result.add(next);
        }
    }

    return result.toArray(new int[result.size()][]);
}
vector<vector<int>> merge(vector<vector<int>>& intervals) {
    if (intervals.empty()) return {};

    sort(intervals.begin(), intervals.end());
    vector<vector<int>> result = {intervals[0]};

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

        if (current[1] >= next[0]) {
            current[1] = max(current[1], next[1]);
        } else {
            result.push_back(next);
        }
    }

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

    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][0] < intervals[j][0]
    })

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

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

        if current[1] >= next[0] {
            current[1] = max(current[1], next[1])
            result[len(result)-1] = current
        } else {
            result = append(result, next)
        }
    }

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

    intervals.sort! { |a, b| a[0] <=> b[0] }
    result = [intervals[0]]

    (1...intervals.length).each do |i|
        current = result[-1]
        next_interval = intervals[i]

        if current[1] >= next_interval[0]
            current[1] = [current[1], next_interval[1]].max
        else
            result << next_interval
        end
    end

    result
end

Meeting Rooms II (Minimum Resources)

For resource allocation problems:

Input: [0,30], [5,10], [15,20]

Step 1: Separate start and end times
starts: [0, 5, 15]
ends:   [10, 20, 30]

Step 2: Two-pointer approach
rooms = 0, endIdx = 0

Process start 0: 0 < 10 ✓ → rooms = 1
Process start 5: 5 < 10 ✓ → rooms = 2
Process start 15: 15 >= 10 ✗ → endIdx = 1, rooms = 2
Process start 20: 20 >= 20 ✗ → endIdx = 2, rooms = 2

Result: 2 rooms needed
function minMeetingRooms(intervals) {
    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 (let start of starts) {
        if (start < ends[endIdx]) {
            rooms++;
        } else {
            endIdx++;
        }
    }

    return rooms;
}
def min_meeting_rooms(intervals):
    starts = sorted(i[0] for i in intervals)
    ends = sorted(i[1] for i in intervals)

    rooms = 0
    end_idx = 0

    for start in starts:
        if start < ends[end_idx]:
            rooms += 1
        else:
            end_idx += 1

    return rooms
public int minMeetingRooms(int[][] intervals) {
    int[] starts = Arrays.stream(intervals).mapToInt(i -> i[0]).sorted().toArray();
    int[] ends = Arrays.stream(intervals).mapToInt(i -> i[1]).sorted().toArray();

    int rooms = 0;
    int endIdx = 0;

    for (int start : starts) {
        if (start < ends[endIdx]) {
            rooms++;
        } else {
            endIdx++;
        }
    }

    return rooms;
}
int minMeetingRooms(vector<vector<int>>& intervals) {
    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]) {
            rooms++;
        } else {
            endIdx++;
        }
    }

    return rooms;
}
func minMeetingRooms(intervals [][]int) int {
    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] {
            rooms++
        } else {
            endIdx++
        }
    }

    return rooms
}
def min_meeting_rooms(intervals)
    starts = intervals.map { |i| i[0] }.sort
    ends = intervals.map { |i| i[1] }.sort

    rooms = 0
    end_idx = 0

    starts.each do |start|
        if start < ends[end_idx]
            rooms += 1
        else
            end_idx += 1
        end
    end

    rooms
end

Practice

Ready to apply these templates? Check out our practice problems to reinforce your understanding and master interval scheduling algorithms.

Pro Tip: Always sort intervals by end time for greedy algorithms and by start time for merging operations. This choice is crucial for optimal solutions.