Lesson 42Advanced58 minAssessment-backed

Intervals and Scheduling

Solve overlap, merge, room allocation, and scheduling problems by sorting intervals around the right event boundary.

What you will be able to do

Model time windows, bookings, incidents, and jobs as intervals.

Choose sort-by-start, sort-by-end, min-heap, or sweep-line based on the question.

Implement merge intervals and meeting-room allocation.

Handle closed/open boundary semantics deliberately.

Connect interval algorithms to calendars, deployment windows, and resource planning.

Intervals are everywhere: calendar events, incident windows, feature rollouts, reservations, TTLs, and deployment freezes. The key is choosing which endpoint makes overlap local.

Endpoint Thinking

Merge intervals by sorting starts. Select maximum compatible meetings by sorting finishes. Count concurrent resources with a min-heap or sweep line. The sort order comes from the operation.

Interval sort orders for merge and scheduling — Different interval questions need different orderings.

Scenario: Deployment Windows

A platform team must merge blocked deployment windows, schedule maintenance jobs, and estimate how many release coordinators are needed during overlap peaks. These are interval problems, but they are not all the same algorithm.

Need	Technique	Why
Merge blocked windows	Sort by start	Overlaps become adjacent.
Max non-overlapping jobs	Sort by finish	Earliest finish leaves most room.
Minimum rooms/workers	Min-heap by end	Track active intervals.
Peak concurrency	Sweep line	Starts and ends change count.

Meeting rooms min heap by end time — A min-heap tracks the resource that becomes free soonest.

Same Pattern in Java, Python, and JavaScript

Merge intervals is the canonical start-sorted interval problem.

import java.util.*;

class MergeIntervalsAnswer {
    static int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
        List<int[]> out = new ArrayList<>();
        for (int[] in : intervals) {
            if (out.isEmpty() || out.get(out.size() - 1)[1] < in[0]) out.add(in);
            else out.get(out.size() - 1)[1] = Math.max(out.get(out.size() - 1)[1], in[1]);
        }
        return out.toArray(new int[out.size()][]);
    }
}

Assessment trap

State whether touching intervals overlap. [1,3] and [3,5] may overlap or not depending on product semantics.

Interview signalFrequently Asked Interview Questions

These are canonical interview patterns for this topic, phrased as concrete problem statements. They avoid vague theory questions and prepare you for the exact reasoning interviewers expect: invariant, edge cases, complexity, and trade-off.

Merge all overlapping intervals.
Return the minimum rooms required for all meetings.
Insert a new interval into sorted non-overlapping intervals and merge if needed.

Production practiceCompany-Style Practice Examples

These are not claimed as exact company-specific questions. They are the interview patterns repeatedly used by product companies to test whether you can move from brute force to a defensible implementation.

Example	Brute-force approach	Stronger solution	Production notes
Deployment freezes	Compare every freeze window pair.	Sort by start and merge adjacent overlaps.	Endpoint semantics affect correctness.
Room allocation	Scan every meeting against every room.	Use min-heap of active end times.	Heap size is current resource demand.
Peak incident load	Store every active interval manually.	Use sweep-line start/end events.	Ordering of equal timestamps must match product meaning.

Solved modelInterview Question Solutions

Question 1: Merge Intervals

Merge all overlapping intervals. Sort by start time, then keep extending the last merged interval while overlap exists.

import java.util.*;

class MergeIntervalsAnswer {
    static int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
        List<int[]> out = new ArrayList<>();
        for (int[] in : intervals) {
            if (out.isEmpty() || out.get(out.size() - 1)[1] < in[0]) out.add(in);
            else out.get(out.size() - 1)[1] = Math.max(out.get(out.size() - 1)[1], in[1]);
        }
        return out.toArray(new int[out.size()][]);
    }
}

Question 2: Meeting Rooms II

Return the minimum rooms required for all meetings. Sort starts and ends independently. A meeting starting before the earliest ending meeting needs a new room; otherwise reuse one.

import java.util.*;
class MeetingRooms { static int minRooms(int[][] intervals) { int n = intervals.length; int[] starts = new int[n], ends = new int[n]; for (int i = 0; i < n; i++) { starts[i] = intervals[i][0]; ends[i] = intervals[i][1]; } Arrays.sort(starts); Arrays.sort(ends); int rooms = 0, end = 0; for (int start : starts) { if (start < ends[end]) rooms++; else end++; } return rooms; } }

Question 3: Insert Interval

Insert a new interval into sorted non-overlapping intervals and merge if needed. Append intervals ending before the new interval, merge all overlaps into the new interval, then append the remaining intervals.

import java.util.*;
class InsertInterval { static int[][] insert(int[][] intervals, int[] next) { List<int[]> out = new ArrayList<>(); int i = 0; while (i < intervals.length && intervals[i][1] < next[0]) out.add(intervals[i++]); while (i < intervals.length && intervals[i][0] <= next[1]) { next[0] = Math.min(next[0], intervals[i][0]); next[1] = Math.max(next[1], intervals[i][1]); i++; } out.add(next); while (i < intervals.length) out.add(intervals[i++]); return out.toArray(new int[out.size()][]); } }

Solved modelWorked Interview Answer

Merge overlapping intervals. Sort by start time so overlaps become adjacent, then merge into the last output interval.

import java.util.*;

class MergeIntervalsAnswer {
    static int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
        List<int[]> out = new ArrayList<>();
        for (int[] in : intervals) {
            if (out.isEmpty() || out.get(out.size() - 1)[1] < in[0]) out.add(in);
            else out.get(out.size() - 1)[1] = Math.max(out.get(out.size() - 1)[1], in[1]);
        }
        return out.toArray(new int[out.size()][]);
    }
}

Hands-on drillTry It Yourself

Practice task

Given intervals [1,3], [2,6], [8,10], [10,12], decide whether touching endpoints merge under closed and half-open semantics.

Failure patternsCommon Mistakes to Avoid

Wrong endpoint semantics.
Using one interval algorithm for every interval problem.
Forgetting to sort first.
Not tracking active resources.
Mutating input when callers expect original order.

Execution guardrailQuick-Start Checklist

Define interval inclusivity.
Choose sort key.
Track current merged interval or active heap.
Handle empty input.
State mutation policy.
State complexity.

Recall drillKnowledge Check

Question	Strong answer
Why sort by start for merge?	Overlaps become adjacent.
Why heap for rooms?	Need earliest finishing active interval.
What is sweep line?	Processing start/end events in order.

VocabularyKey Terms

Term	Meaning
Interval	Range with start and end.
Overlap	Ranges sharing time or space under chosen semantics.
Sweep line	Ordered processing of boundary events.
Active set	Intervals currently open.

Next practiceFurther Reading

Practice merge intervals, insert interval, meeting rooms, and employee free time.
Review priority queues.
Compare closed and half-open time ranges.

Greedy Choice and Proof

Topological Sort