Interval Problems
interval-problems
Algorithms
Greedy (Intro)
Given coin denominations of 1, 5, and 25, the greedy "take the largest coin that fits" strategy gives change optimally. Add a coin worth 10 to the system and greedy stays optimal. Replace 25 with 21 and greedy quietly breaks: making 63 cents now wants three 21s, but greedy says one 21 plus two 1s and ten more 1s. The same algorithm, the same input shape, and yet correctness depends entirely on a structural property of the problem. **Greedy (Intro)** explains exactly which property that is. You will learn to test for the greedy-choice property and optimal substructure, the twin ingredients that justify a greedy decision. The lesson covers the canonical problems where greedy provably works (activity selection by earliest end time, fractional knapsack by value-to-weight ratio, job scheduling with deadlines, the jump game, Huffman encoding) and walks through the exchange-argument style of correctness proof. It also shows where greedy fails (0/1 knapsack, coin change with arbitrary denominations) so you know when to reach for DP instead. In **Sorting (Elementary)**, you saw why sorting often costs `O(n log n)`; almost every greedy algorithm starts with a sort step. **Big-O Notation (Upper Bound)** gave you the language to express that cost. Next, **Dynamic Programming (Intro)** picks up where greedy fails, when the local optimum does not guarantee the global one.
Not Started
0%
Practice Problems
Meeting Rooms
Given an array of meeting time intervals, determine if a person could attend all meetings without any overlap.
Summary Ranges
Given a sorted unique integer array, return the smallest sorted list of ranges that cover all the numbers in the array.
Minimum Interval to Include Each Query
Given a list of intervals and a list of queries, for each query find the size of the smallest interval that contains it, or -1 if no interval contains it.
Insert Interval
Given a set of non-overlapping intervals sorted by start time and a new interval, insert the new interval and merge if necessary.
Meeting Rooms II
Given an array of meeting time intervals, determine the minimum number of conference rooms required to hold all meetings.
Merge Intervals
Given an array of intervals, merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input.
Minimum Arrows to Burst Balloons
Given balloons represented as horizontal intervals, find the minimum number of vertical arrows needed to burst all balloons.
Non-overlapping Intervals
Given an array of intervals, return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.