Interval Scheduling

Weighted and unweighted interval scheduling variants.

6 min readMastering Data Structures & Algorithms for Software Engineering InterviewsCode

Unweighted (Activity Selection)

Maximize count of non-overlapping intervals. Earliest finish time greedy works. O(n log n) for sort.

Weighted Interval Scheduling

Each interval has value/weight. Maximize total weight of non-overlapping intervals. Greedy fails. Use DP: sort by finish, for each interval find previous compatible (binary search). DP[i] = max(weight[i] + DP[prev(i)], DP[i-1]).

Goweighted-interval-scheduling-dp.go

35 linesLn 1, Col 1Go

DP[i] = max weight using first i intervals. For interval i (1-indexed): include it + best compatible before it, or skip it. prev[i] finds last compatible via binary search in O(log n) for O(n log n) total.

Interval Partitioning

Schedule all intervals using minimum number of resources (rooms). Equivalent to finding max concurrent intervals. Greedy: sort by start time, assign each to first available room (min-heap of room end times).

Gointerval-partitioning.go

29 linesLn 1, Col 1Go

Sweep line: process start/end events. Increment rooms on start, decrement on end. Max concurrent = min rooms needed. O(n log n).

Mark this lesson complete to store local progress and unlock a cleaner resume path the next time you visit.