Problems

Master interval scheduling algorithms by solving these carefully selected problems. Each problem demonstrates different aspects of greedy algorithms, dynamic programming, and resource allocation techniques.

Ready to apply your interval scheduling knowledge? This page contains curated problems organized by difficulty, each with detailed explanations and multi-language solutions. Use these problems to reinforce the concepts from our concept guide and code templates.

Problem List

Easy Problems

1. Meeting Rooms

Brief: Determine if a person could attend all meetings given an array of meeting time intervals.

Why this pattern?: This is a classic overlap detection problem where we need to check if any two meetings conflict.

Key Insight: Sort meetings by start time and check if any meeting starts before the previous one ends.

Visual Algorithm Flow:

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

Step 1: Sort by start time
Sorted: [0,30], [5,10], [15,20]

Step 2: Check consecutive overlaps
Process [0,30] and [5,10]: 5 < 30 ✓ → Conflict detected
Result: false (cannot attend all meetings)

Code Solution:

function canAttendMeetings(intervals) {
    intervals.sort((a, b) => a.start - b.start);

    for (let i = 1; i < intervals.length; i++) {
        if (intervals[i].start < intervals[i-1].end) {
            return false;
        }
    }

    return true;
}

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

    for i in range(1, len(intervals)):
        if intervals[i][0] < intervals[i-1][1]:
            return False

    return True

public boolean canAttendMeetings(int[][] intervals) {
    Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));

    for (int i = 1; i < intervals.length; i++) {
        if (intervals[i][0] < intervals[i-1][1]) {
            return false;
        }
    }

    return true;
}

bool canAttendMeetings(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end());

    for (size_t i = 1; i < intervals.size(); ++i) {
        if (intervals[i][0] < intervals[i-1][1]) {
            return false;
        }
    }

    return true;
}

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

    for i := 1; i < len(intervals); i++ {
        if intervals[i][0] < intervals[i-1][1] {
            return false
        }
    }

    return true
}

def can_attend_meetings(intervals)
    intervals.sort! { |a, b| a[0] <=> b[0] }

    (1...intervals.length).each do |i|
        return false if intervals[i][0] < intervals[i-1][1]
    end

    true
end

2. Merge Intervals

Brief: Given a collection of intervals, merge all overlapping intervals.

Why this pattern?: This problem requires combining overlapping intervals into larger continuous intervals.

Key Insight: Sort by start time, then merge intervals that overlap by extending the end time.

Visual Algorithm Flow:

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]

Code Solution:

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

Medium Problems

3. Non-overlapping Intervals

Brief: Find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Why this pattern?: This is an optimization problem where we want to keep the maximum number of non-overlapping intervals.

Key Insight: Use greedy approach - sort by end time and always pick the interval that ends earliest.

Visual Algorithm Flow:

Input: [1,2], [2,3], [3,4], [1,3]

Step 1: Sort by end time
Sorted: [1,2], [2,3], [3,4], [1,3]

Step 2: Greedy selection
count = 0, prevEnd = -∞

Process [1,2]: 1 >= -∞ ✓ → prevEnd = 2
Process [2,3]: 2 >= 2 ✓ → prevEnd = 3
Process [3,4]: 3 >= 3 ✓ → prevEnd = 4
Process [1,3]: 1 < 4 ✗ → count = 1 (remove [1,3])

Result: 1 interval needs to be removed

Code Solution:

function eraseOverlapIntervals(intervals) {
    intervals.sort((a, b) => a.end - b.end);

    let count = 0;
    let prevEnd = -Infinity;

    for (const interval of intervals) {
        if (interval.start < prevEnd) {
            count++;
        } else {
            prevEnd = interval.end;
        }
    }

    return count;
}

def erase_overlap_intervals(intervals):
    intervals.sort(key=lambda x: x[1])

    count = 0
    prev_end = float('-inf')

    for interval in intervals:
        if interval[0] < prev_end:
            count += 1
        else:
            prev_end = interval[1]

    return count

public int eraseOverlapIntervals(int[][] intervals) {
    Arrays.sort(intervals, Comparator.comparingInt(a -> a[1]));

    int count = 0;
    int prevEnd = Integer.MIN_VALUE;

    for (int[] interval : intervals) {
        if (interval[0] < prevEnd) {
            count++;
        } else {
            prevEnd = interval[1];
        }
    }

    return count;
}

int eraseOverlapIntervals(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end(),
         [](const vector<int>& a, const vector<int>& b) {
             return a[1] < b[1];
         });

    int count = 0;
    int prevEnd = INT_MIN;

    for (const auto& interval : intervals) {
        if (interval[0] < prevEnd) {
            count++;
        } else {
            prevEnd = interval[1];
        }
    }

    return count;
}

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

    count := 0
    prevEnd := math.MinInt32

    for _, interval := range intervals {
        if interval[0] < prevEnd {
            count++
        } else {
            prevEnd = interval[1]
        }
    }

    return count
}

def erase_overlap_intervals(intervals)
    intervals.sort! { |a, b| a[1] <=> b[1] }

    count = 0
    prev_end = -Float::INFINITY

    intervals.each do |interval|
        if interval[0] < prev_end
            count += 1
        else
            prev_end = interval[1]
        end
    end

    count
end

4. Meeting Rooms II

Brief: Find the minimum number of conference rooms required for given meetings.

Why this pattern?: This is a resource allocation problem where we need to track concurrent meetings.

Key Insight: Use two arrays for start and end times, then use two pointers to track room allocation.

Visual Algorithm Flow:

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

Code Solution:

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

5. Car Pooling

Brief: Determine if a car can handle all pickups/dropoffs within capacity constraints.

Why this pattern?: This is an event processing problem where we track passenger changes over time.

Key Insight: Create events for pickups and dropoffs, sort by location, and track cumulative passengers.

Visual Algorithm Flow:

Input: trips = [[2,1,5], [3,3,7]], capacity = 4

Step 1: Create pickup/dropoff events
events = [[1, 2], [5, -2], [3, 3], [7, -3]]

Step 2: Sort events by location
sorted = [[1, 2], [3, 3], [5, -2], [7, -3]]

Step 3: Process events in order
current = 0

Process [1, 2]: current = 2 (2 <= 4 ✓)
Process [3, 3]: current = 5 (5 > 4 ✗) → Return false

Code Solution:

function carPooling(trips, capacity) {
    const events = [];

    for (const [num, start, end] of trips) {
        events.push([start, num]);    // pickup
        events.push([end, -num]);     // dropoff
    }

    events.sort((a, b) => a[0] - b[0] || a[1] - b[1]);

    let current = 0;
    for (const [location, change] of events) {
        current += change;
        if (current > capacity) return false;
    }

    return true;
}

def car_pooling(trips, capacity):
    events = []

    for num, start, end in trips:
        events.append((start, num))    # pickup
        events.append((end, -num))     # dropoff

    events.sort(key=lambda x: (x[0], x[1]))

    current = 0
    for location, change in events:
        current += change
        if current > capacity:
            return False

    return True

public boolean carPooling(int[][] trips, int capacity) {
    List<int[]> events = new ArrayList<>();

    for (int[] trip : trips) {
        events.add(new int[]{trip[1], trip[0]});    // pickup [location, passengers]
        events.add(new int[]{trip[2], -trip[0]});   // dropoff [location, -passengers]
    }

    events.sort(Comparator.comparingInt(a -> a[0]));

    int current = 0;
    for (int[] event : events) {
        current += event[1];
        if (current > capacity) return false;
    }

    return true;
}

bool carPooling(vector<vector<int>>& trips, int capacity) {
    vector<pair<int, int>> events;

    for (const auto& trip : trips) {
        events.emplace_back(trip[1], trip[0]);     // pickup
        events.emplace_back(trip[2], -trip[0]);    // dropoff
    }

    sort(events.begin(), events.end());

    int current = 0;
    for (const auto& event : events) {
        current += event.second;
        if (current > capacity) return false;
    }

    return true;
}

func carPooling(trips [][]int, capacity int) bool {
    events := make([][2]int, 0, len(trips)*2)

    for _, trip := range trips {
        events = append(events, [2]int{trip[1], trip[0]})     // pickup
        events = append(events, [2]int{trip[2], -trip[0]})    // dropoff
    }

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

    current := 0
    for _, event := range events {
        current += event[1]
        if current > capacity {
            return false
        }
    }

    return true
}

def car_pooling(trips, capacity)
    events = []

    trips.each do |num, start, end|
        events << [start, num]     # pickup
        events << [end, -num]      # dropoff
    end

    events.sort!

    current = 0
    events.each do |location, change|
        current += change
        return false if current > capacity
    end

    true
end

Hard Problems

6. Course Schedule III

Brief: Schedule courses with durations and deadlines to maximize the number of courses completed.

Why this pattern?: This is a weighted interval scheduling problem with deadlines.

Key Insight: Sort by deadline, use max heap to replace longer courses when capacity is exceeded.

Visual Algorithm Flow:

Input: courses = [[100,200], [200,1300], [1000,1250], [2000,3200]]

Step 1: Sort by deadline
Sorted: [[100,200], [1000,1250], [200,1300], [2000,3200]]

Step 2: Process each course
time = 0, heap = []

Process [100,200]: time = 100 (100 <= 200 ✓) → heap = [100]
Process [1000,1250]: time = 1100 (1100 <= 1250 ✓) → heap = [100, 1000]
Process [200,1300]: time = 1300 (1300 <= 1300 ✓) → heap = [100, 1000, 200]
Process [2000,3200]: time = 3300 (3300 > 3200 ✗) → Remove 1000 → time = 2300 → heap = [100, 200, 2000]

Result: 3 courses can be completed

Code Solution:

function scheduleCourse(courses) {
    // Sort by deadline
    courses.sort((a, b) => a[1] - b[1]);

    const maxHeap = new MaxPriorityQueue({priority: (a, b) => a - b});
    let time = 0;

    for (const [duration, deadline] of courses) {
        time += duration;
        maxHeap.enqueue(duration);

        // If over deadline, remove longest course
        if (time > deadline) {
            time -= maxHeap.dequeue().element;
        }
    }

    return maxHeap.size();
}

import heapq

def schedule_course(courses):
    # Sort by deadline
    courses.sort(key=lambda x: x[1])

    heap = []
    time = 0

    for duration, deadline in courses:
        time += duration
        heapq.heappush(heap, -duration)  # max heap using negative values

        # If over deadline, remove longest course
        if time > deadline:
            time += heapq.heappop(heap)  # Remove negative duration

    return len(heap)

public int scheduleCourse(int[][] courses) {
    // Sort by deadline
    Arrays.sort(courses, Comparator.comparingInt(a -> a[1]));

    PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
    int time = 0;

    for (int[] course : courses) {
        int duration = course[0];
        int deadline = course[1];

        time += duration;
        maxHeap.offer(duration);

        // If over deadline, remove longest course
        if (time > deadline) {
            time -= maxHeap.poll();
        }
    }

    return maxHeap.size();
}

int scheduleCourse(vector<vector<int>>& courses) {
    // Sort by deadline
    sort(courses.begin(), courses.end(),
         [](const vector<int>& a, const vector<int>& b) {
             return a[1] < b[1];
         });

    priority_queue<int> maxHeap;
    int time = 0;

    for (const auto& course : courses) {
        int duration = course[0];
        int deadline = course[1];

        time += duration;
        maxHeap.push(duration);

        // If over deadline, remove longest course
        if (time > deadline) {
            time -= maxHeap.top();
            maxHeap.pop();
        }
    }

    return maxHeap.size();
}

import "container/heap"

type MaxHeap []int

func (h MaxHeap) Len() int           { return len(h) }
func (h MaxHeap) Less(i, j int) bool { return h[i] > h[j] }
func (h MaxHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *MaxHeap) Push(x interface{}) {
    *h = append(*h, x.(int))
}

func (h *MaxHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

func scheduleCourse(courses [][]int) int {
    // Sort by deadline
    sort.Slice(courses, func(i, j int) bool {
        return courses[i][1] < courses[j][1]
    })

    maxHeap := &MaxHeap{}
    heap.Init(maxHeap)
    time := 0

    for _, course := range courses {
        duration := course[0]
        deadline := course[1]

        time += duration
        heap.Push(maxHeap, duration)

        // If over deadline, remove longest course
        if time > deadline {
            time -= heap.Pop(maxHeap).(int)
        }
    }

    return maxHeap.Len()
}

def schedule_course(courses)
    # Sort by deadline
    courses.sort! { |a, b| a[1] <=> b[1] }

    heap = []
    time = 0

    courses.each do |duration, deadline|
        time += duration
        heap << duration
        heap.sort!.reverse!  # Max heap

        # If over deadline, remove longest course
        if time > deadline
            time -= heap.shift
        end
    end

    heap.length
end

Recommended Study Order

Start with Meeting Rooms to grasp basic overlap detection
Move to Merge Intervals for interval combination techniques
Practice Non-overlapping Intervals for greedy selection
Tackle Meeting Rooms II for resource allocation
Try Car Pooling for event processing
Challenge yourself with Course Schedule III for weighted scheduling

Practice Tips

Time yourself: Aim to solve each problem within 20-30 minutes
Explain your approach: Practice explaining the algorithm out loud
Edge cases: Always consider empty input, single intervals, and boundary conditions
Space optimization: Look for ways to reduce space complexity where possible

Ready to test your skills? Start with the easy problems and work your way up to the hard ones!

Pro Tip: Most interval problems become easier when you sort by end time. This greedy choice leads to optimal solutions in many scheduling scenarios.