6a:T5fd,def minimum_points_to_pierce(intervals: list[tuple[int, int]]) -> list[int]: """ Find minimum points to pierce all intervals. Each interval [start, end] must contain at least one point. Returns the list of point positions. Time: O(n log n) for sorting, O(n) for single pass Space: O(n) for result (could be O(1) if returning count only) """ if not intervals: return [] # Sort by right endpoint (end time) sorted_intervals = sorted(intervals, key=lambda x: x[1]) points = [] last_point = float('-inf') # No point placed yet for start, end in sorted_intervals: # If this interval is not covered by the last point if start > last_point: # Place a new point at the right endpoint last_point = end points.append(last_point) return points def minimum_points_count(intervals: list[tuple[int, int]]) -> int: """Space-optimized version returning only the count.""" if not intervals: return 0 sorted_intervals = sorted(intervals, key=lambda x: x[1]) count = 0 last_point = float('-inf') for start, end in sorted_intervals: if start > last_point: last_point = end count += 1 return count # Example usage intervals = [(1, 4), (2, 6), (5, 7), (6, 9), (8, 10)] points = minimum_points_to_pierce(intervals) print(f"Points needed: {points}") # Output: [4, 7, 10] print(f"Minimum count: {len(points)}") # Output: 36b:T5d4,type Interval = [number, number]; function minimumPointsToPierce(intervals: Interval[]): number[] { /** * Find minimum points to pierce all intervals. * * Time: O(n log n) for sorting, O(n) for iteration * Space: O(n) for result */ if (intervals.length === 0) return []; // Sort by right endpoint const sorted = [...intervals].sort((a, b) => a[1] - b[1]); const points: number[] = []; let lastPoint = -Infinity; for (const [start, end] of sorted) { // If this interval starts after our last point, need new point if (start > lastPoint) { lastPoint = end; // Place at right endpoint points.push(lastPoint); } } return points; } function minimumPointsCount(intervals: Interval[]): number { /** * Space-optimized version returning only count. * Useful when actual positions aren't needed. */ if (intervals.length === 0) return 0; const sorted = [...intervals].sort((a, b) => a[1] - b[1]); let count = 0; let lastPoint = -Infinity; for (const [start, end] of sorted) { if (start > lastPoint) { lastPoint = end; count++; } } return count; } // Example const intervals: Interval[] = [[1, 4], [2, 6], [5, 7], [6, 9], [8, 10]]; console.log("Points:", minimumPointsToPierce(intervals)); // [4, 7, 10] console.log("Count:", minimumPointsCount(intervals)); // 36c:T7ae,import java.util.*; public class IntervalStabbing { public static List minimumPointsToPierce(int[][] intervals) { /** * Find minimum points to pierce all intervals. * * @param intervals Each interval is [start, end] * @return List of point positions that pierce all intervals * * Time: O(n log n), Space: O(n) */ if (intervals == null || intervals.length == 0) { return Collections.emptyList(); } // Sort by right endpoint int[][] sorted = intervals.clone(); Arrays.sort(sorted, (a, b) -> Integer.compare(a[1], b[1])); List points = new ArrayList<>(); int lastPoint = Integer.MIN_VALUE; for (int[] interval : sorted) { int start = interval[0], end = interval[1]; // If not covered by last point if (start > lastPoint) { lastPoint = end; // Place at right endpoint points.add(lastPoint); } } return points; } public static int minimumPointsCount(int[][] intervals) { if (intervals == null || intervals.length == 0) return 0; int[][] sorted = intervals.clone(); Arrays.sort(sorted, (a, b) -> Integer.compare(a[1], b[1])); int count = 0; int lastPoint = Integer.MIN_VALUE; for (int[] interval : sorted) { if (interval[0] > lastPoint) { lastPoint = interval[1]; count++; } } return count; } public static void main(String[] args) { int[][] intervals = {{1, 4}, {2, 6}, {5, 7}, {6, 9}, {8, 10}}; System.out.println("Points: " + minimumPointsToPierce(intervals)); System.out.println("Count: " + minimumPointsCount(intervals)); } }6d:T5d9,**Detailed Proof:** Let intervals be sorted by right endpoint: `I₁, I₂, ..., Iₙ` where `e₁ ≤ e₂ ≤ ... ≤ eₙ`. **Step 1: First Interval Analysis** Consider interval `I₁ = [s₁, e₁]`. Any valid solution must have a point `p` such that `s₁ ≤ p ≤ e₁`. The greedy algorithm places its point at `e₁`. If `OPT` has a point `p < e₁` covering `I₁`, we can move `p` to `e₁`. This maintains coverage of `I₁` (since `e₁ ∈ [s₁, e₁]`) and can only improve coverage of other intervals (pushing right never "exits" an interval earlier than necessary). **Step 2: Coverage Monotonicity** If point `p` covers interval `[s, e]` (meaning `s ≤ p ≤ e`) and we move `p` to a larger value `p'` with `p ≤ p' ≤ e`, then: - We still have `s ≤ p' ≤ e` (stays in the interval) - Any interval `[s', e']` with `s' ≤ p` and `e' ≥ p'` is still covered Since we sorted by right endpoint, all "later" intervals have `eⱼ ≥ e₁`. If a later interval `Iⱼ` was covered by a point in `OPT`, moving that point rightward (but not past the interval's right endpoint) maintains coverage. **Step 3: Inductive Transformation** After placing the greedy point at `e₁`: - Remove all intervals covered by this point (those with `sⱼ ≤ e₁`, which includes `I₁`) - Apply the same argument to the remaining intervals At each step, `OPT` can be transformed to match `GREEDY`'s choice, point by point. Since transformations never add points, `|GREEDY| ≤ |OPT|`.6e:T80f,def min_intervals_to_cover_range( target_start: int, target_end: int, intervals: list[tuple[int, int]] ) -> list[tuple[int, int]] | None: """ Find minimum intervals to cover the range [target_start, target_end]. Returns list of selected intervals, or None if coverage is impossible. Strategy: Greedy by "furthest reach" at each step. Time: O(n log n) for sorting, O(n) for selection """ if not intervals: return None if target_start < target_end else [] # Sort by start point sorted_intervals = sorted(intervals, key=lambda x: x[0]) result = [] current_end = target_start # Coverage achieved so far i = 0 n = len(sorted_intervals) while current_end < target_end: # Find the interval that starts at or before current_end # and extends the furthest furthest_end = current_end best_interval = None while i < n and sorted_intervals[i][0] <= current_end: start, end = sorted_intervals[i] if end > furthest_end: furthest_end = end best_interval = sorted_intervals[i] i += 1 # If we couldn't extend, there's a gap if furthest_end == current_end: return None # Impossible to cover # Select this interval result.append(best_interval) current_end = furthest_end return result def min_intervals_count( target_start: int, target_end: int, intervals: list[tuple[int, int]] ) -> int: """Returns just the count, or -1 if impossible.""" result = min_intervals_to_cover_range(target_start, target_end, intervals) return len(result) if result is not None else -1 # Example target = (0, 10) intervals = [(0, 3), (2, 5), (4, 7), (6, 9), (8, 10)] coverage = min_intervals_to_cover_range(target[0], target[1], intervals) if coverage: print(f"Intervals needed: {coverage}") print(f"Count: {len(coverage)}") else: print("Coverage impossible!")6f:T695,type Interval = [number, number]; function minIntervalsToCoverRange( targetStart: number, targetEnd: number, intervals: Interval[] ): Interval[] | null { /** * Find minimum intervals to cover [targetStart, targetEnd]. * * Uses greedy "furthest reach" strategy. * Time: O(n log n), Space: O(n) for result */ if (intervals.length === 0) { return targetStart >= targetEnd ? [] : null; } // Sort by start point const sorted = [...intervals].sort((a, b) => a[0] - b[0]); const result: Interval[] = []; let currentEnd = targetStart; // Coverage so far let i = 0; while (currentEnd < targetEnd) { // Find interval starting <= currentEnd with furthest reach let furthestEnd = currentEnd; let bestInterval: Interval | null = null; while (i < sorted.length && sorted[i][0] <= currentEnd) { const [start, end] = sorted[i]; if (end > furthestEnd) { furthestEnd = end; bestInterval = sorted[i]; } i++; } // Gap detected if (furthestEnd === currentEnd) { return null; // Impossible } result.push(bestInterval!); currentEnd = furthestEnd; } return result; } // Example const target: [number, number] = [0, 10]; const intervals: Interval[] = [[0, 3], [2, 5], [4, 7], [6, 9], [8, 10]]; const coverage = minIntervalsToCoverRange(target[0], target[1], intervals); console.log(coverage ? `Intervals: ${JSON.stringify(coverage)}, Count: ${coverage.length}` : "Coverage impossible!");70:T56c,Why does the "furthest reach" strategy produce an optimal solution? Again, we use the exchange argument. **Claim:** The greedy algorithm produces a minimum-size covering, or correctly reports impossibility. **Proof Sketch (Exchange Argument):** Consider any optimal solution `OPT = {I₁*, I₂*, ..., Iₖ*}` ordered by the sequence in which they cover the target range. **Step 1: First Interval** The first interval in `OPT` must start at or before `T_start`. Among all such intervals, suppose `OPT` chose interval `I₁*` with endpoint `e₁*`. The greedy algorithm chooses the interval with the **furthest endpoint** among those starting at or before `T_start`. Call this `G₁` with endpoint `g₁`. By definition, `g₁ ≥ e₁*`. If we replace `I₁*` with `G₁` in `OPT`, we get a solution that: - Still covers from `T_start` to at least `e₁*` (actually to `g₁ ≥ e₁*`) - Uses the same number of intervals - Has coverage at least as far as before **Step 2: Subsequent Intervals** After the first interval, we need to cover from `g₁` (or `e₁*`) onward. By the same argument, the greedy choice of "furthest reach among valid starters" can replace `OPT`'s choice without harm. **Step 3: Termination** Since greedy always reaches at least as far as `OPT` at each step, greedy terminates with at most as many intervals as `OPT`. Therefore, `|GREEDY| ≤ |OPT|`.71:T80a,def test_interval_stabbing_edge_cases(): """Test edge cases for interval stabbing.""" from interval_stabbing import minimum_points_to_pierce # Empty input assert minimum_points_to_pierce([]) == [] # Single interval assert len(minimum_points_to_pierce([(5, 10)])) == 1 # All intervals share point 5 intervals = [(1, 5), (3, 7), (5, 10), (5, 8)] points = minimum_points_to_pierce(intervals) assert len(points) == 1 assert all(s <= points[0] <= e for s, e in intervals) # No overlap - need all points intervals = [(1, 2), (3, 4), (5, 6), (7, 8)] assert len(minimum_points_to_pierce(intervals)) == 4 # Complete overlap (nested intervals) intervals = [(1, 10), (2, 9), (3, 8), (4, 7)] points = minimum_points_to_pierce(intervals) assert len(points) == 1 # Point must be in innermost interval [4, 7] assert 4 <= points[0] <= 7 def test_range_covering_edge_cases(): """Test edge cases for range covering.""" from range_covering import min_intervals_to_cover_range # Empty target (start >= end) assert min_intervals_to_cover_range(5, 5, [(1, 10)]) == [] assert min_intervals_to_cover_range(5, 3, [(1, 10)]) == [] # No interval covers start result = min_intervals_to_cover_range(0, 10, [(5, 15), (7, 20)]) assert result is None # Gap at [0, 5) # Gap in middle result = min_intervals_to_cover_range(0, 10, [(0, 3), (5, 10)]) assert result is None # Gap at (3, 5) # One interval covers exactly result = min_intervals_to_cover_range(0, 10, [(0, 10)]) assert result == [(0, 10)] # Redundant intervals (more than needed) intervals = [(0, 5), (0, 6), (4, 10), (5, 10), (3, 10)] result = min_intervals_to_cover_range(0, 10, intervals) # Should select [0, 6] and [3, 10] or similar optimal pair assert len(result) == 2 if __name__ == "__main__": test_interval_stabbing_edge_cases() test_range_covering_edge_cases() print("All edge case tests passed!")63:{"json":{"id":"seed_2ee8d19d0adf33c9a93d7ca9122be2ca","slug":"interval-scheduling-patterns","category":"Data Structures & Algorithms","topic":"Interval Scheduling Patterns","title":"Interval Scheduling Patterns","description":"Master the rich family of interval-based greedy problems including covering, meeting rooms, resource allocation, and event-based sweeping techniques. Learn to recognize, model, and solve problems involving overlapping time ranges, resource constraints, and scheduling optimization.","difficulty":"INTERMEDIATE","estimatedMinutes":75,"pages":[{"id":"seed_02941fef50f95f4265019692c7c43ede","title":"Interval Covering Problems","order":0,"content":[{"id":"opening-hook","title":"Beyond Activity Selection: The Covering Perspective","content":[{"data":{"content":"In the Activity Selection Problem, we asked: *\"How many non-overlapping activities can we fit?\"* We selected a maximum subset while avoiding conflicts. But interval scheduling encompasses a much richer family of problems—problems that ask the **inverse question**: instead of *avoiding* overlap, what if we want to *ensure* coverage?\n\n**Interval covering problems** flip the script. Rather than selecting intervals that don't touch, we want to cover a target—either by placing points that \"pierce\" every interval, or by selecting intervals that together span an entire range. These problems arise constantly in practice: ensuring security cameras cover all hallways, scheduling inspections that catch every flight, or placing sensors along a pipeline to monitor every segment."},"type":"text"},{"data":{"icon":"Target","title":"What You Will Learn","content":"By the end of this page, you will understand the covering perspective on intervals, master the 'minimum points to pierce all intervals' problem with its greedy proof, solve the 'minimum intervals to cover a range' problem, recognize the duality between covering and packing problems, and build intuition for when greedy works in covering contexts.","variant":"info"},"type":"callout"}]},{"id":"covering-paradigm","title":"The Covering Paradigm","content":[{"data":{"content":"To understand interval covering, we must first clarify what \"covering\" means in this context. There are two fundamental covering questions:\n\n**Type 1: Points covering intervals (Interval Stabbing)**\n\nGiven a set of intervals, find the **minimum number of points** such that every interval contains at least one point. Each point \"stabs\" or \"pierces\" the intervals it lies within.\n\n**Type 2: Intervals covering a range (Set Cover on Intervals)**\n\nGiven a set of available intervals and a target range, find the **minimum number of intervals** whose union covers the entire target range.\n\nBoth problems have elegant greedy solutions, but the strategies differ significantly. Let's build deep understanding of each."},"type":"text"},{"data":{"rows":[["Objective","Maximize selected intervals","Minimize points/intervals used"],["Constraint","Selected intervals don't overlap","Every input interval must be covered"],["Overlap is...","Forbidden (conflict)","Required (intersections enable coverage)"],["Greedy metric","Sort by end time, select non-overlapping","Sort by end time, place point at end, skip covered"],["Typical application","Scheduling without conflicts","Inspection, surveillance, monitoring"]],"caption":"Covering vs. Packing: The Duality of Interval Problems","headers":["Aspect","Packing (Activity Selection)","Covering (Interval Stabbing)"]},"type":"table"},{"data":{"content":"**The Mathematical Duality**\n\nThere's a beautiful relationship between packing and covering. In graph theory terms, the maximum independent set (packing) and the minimum vertex cover are dual problems. For intervals, a similar relationship exists:\n\n- The **maximum number of pairwise non-overlapping intervals** equals the **minimum number of points needed to stab all intervals** in certain configurations.\n\nThis isn't always exact, but the intuition helps: if no two intervals overlap, you need one point per interval—exactly the count of selected intervals in activity selection. When intervals do overlap, shared points reduce the count below the total number of intervals."},"type":"text"},{"data":{"icon":"Lightbulb","title":"Recognizing Covering Problems","content":"If a problem asks for 'minimum resources to monitor/inspect/catch everything' or 'fewest intervals to span a range,' you're likely facing a covering problem. The key signal is that coverage must be complete—no gaps allowed—while the objective is minimization.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":1},{"id":"minimum-points-pierce","title":"Minimum Points to Pierce All Intervals","content":[{"data":{"content":"This problem is sometimes called \"Interval Stabbing\" or \"Minimum Hitting Set for Intervals.\" Given `n` intervals, we want the fewest points on the number line such that every interval contains at least one point.\n\n**Problem Statement (Formal)**\n\nInput: A set of `n` intervals `I = {[s₁, e₁], [s₂, e₂], ..., [sₙ, eₙ]}`\n\nOutput: A minimum-size set of points `P = {p₁, p₂, ..., pₖ}` such that for every interval `[sᵢ, eᵢ]`, there exists some `pⱼ ∈ P` with `sᵢ ≤ pⱼ ≤ eᵢ`.\n\n**Example: Flight Inspections**\n\nImagine you're an airport security inspector. Each flight has a time window during which it's at the gate (its interval). You want to schedule the minimum number of inspection times such that every flight gets inspected at least once during its gate time."},"type":"text"},{"data":{"input":"Intervals: [1, 4], [2, 6], [5, 7], [6, 9], [8, 10]","title":"Interval Stabbing Example","output":"Minimum points: {4, 7, 10} (or {4, 6, 10}) — 3 points","description":"Finding minimum points to pierce all intervals","explanation":"Point 4 covers [1,4] and [2,6]. Point 7 covers [5,7] and [6,9]. Point 10 covers [8,10]. No single placement of 2 points can cover all 5 intervals."},"type":"example"},{"data":{"content":"**The Greedy Strategy: Place at Right Endpoints**\n\nThe greedy algorithm for interval stabbing is elegantly simple:\n\n1. **Sort intervals by their right endpoint** (end time)\n2. **Initialize** an empty set of points and track the \"last placed point\"\n3. **Iterate** through intervals in sorted order:\n - If the current interval is NOT already covered (its start > last placed point):\n - Place a new point at this interval's **right endpoint**\n - Update last placed point\n4. **Return** the set of placed points\n\nThis greedy choice—placing the point as far right as possible within the current interval—maximizes the chance that subsequent intervals will also be covered by this same point."},"type":"text"},{"data":{"fileName":"interval_stabbing.py","languages":[{"code":"$6a","label":"Python","value":"python"},{"code":"$6b","label":"TypeScript","value":"typescript"},{"code":"$6c","label":"Java","value":"java"}]},"type":"code"}],"titleType":"number","titleNumber":2},{"id":"proof-correctness","title":"Proof of Correctness for Interval Stabbing","content":[{"data":{"content":"Why does placing points at right endpoints work? Let's prove this rigorously using the **exchange argument**—the same technique we've seen for other greedy problems.\n\n**Claim:** The greedy algorithm produces an optimal solution (minimum number of points).\n\n**Proof Outline:**\n\nWe'll show that any optimal solution `OPT` can be transformed into the greedy solution `GREEDY` without increasing the number of points. This proves `|GREEDY| ≤ |OPT|`, and since `GREEDY` is a valid solution, we have `|OPT| ≤ |GREEDY|`, thus `|GREEDY| = |OPT|`."},"type":"text"},{"data":{"icon":"Info","title":"The Exchange Argument Structure","content":"1. Consider the first interval in sorted order (smallest right endpoint). 2. Any solution must have a point that covers it. 3. Moving that point to the right endpoint never harms coverage (it stays within the first interval and potentially covers more). 4. Apply inductively to remaining intervals.","variant":"note"},"type":"callout"},{"data":{"content":"$6d"},"type":"text"},{"data":{"items":["**Right endpoint is the 'greedy-safe' position** — Placing here maximizes future interval coverage without risking the current interval.","**Sorting by end time is essential** — It ensures we handle the 'most constrained' intervals first (those that end earliest).","**Exchange argument applicability** — Works because moving points rightward within valid bounds never harms the solution.","**Greedy choice property holds** — Each local decision (place at right endpoint) contributes to a global optimum."],"title":{"icon":"CheckCircle","text":"Key Proof Insights","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"icon":"AlertCircle","title":"Common Mistake: Placing at Left Endpoint","content":"Placing points at the LEFT endpoint does NOT work. Consider intervals [1, 5] and [3, 4]. Placing at start of [3, 4] gives point 3, which covers both. But placing at start of [1, 5] (sorted by left endpoint, point = 1) covers only [1, 5], requiring another point for [3, 4]. The sorted-by-end-time invariant is crucial.","variant":"warning"},"type":"callout"}],"titleType":"number","titleNumber":3},{"id":"minimum-intervals-cover","title":"Minimum Intervals to Cover a Range","content":[{"data":{"content":"The second major covering problem asks: given a set of intervals and a **target range** `[T_start, T_end]`, what's the minimum number of intervals whose union covers the entire target?\n\n**Problem Statement (Formal)**\n\nInput: \n- A target range `[T_start, T_end]`\n- A set of `n` intervals `{[s₁, e₁], [s₂, e₂], ..., [sₙ, eₙ]}`\n\nOutput: A minimum-size subset of intervals whose union contains every point in `[T_start, T_end]`, or indication that coverage is impossible.\n\n**Example: Pipeline Monitoring**\n\nImagine a 100-meter pipeline that needs sensor coverage. Available sensors have different coverage ranges. We want to select the fewest sensors that monitor the entire pipeline without gaps."},"type":"text"},{"data":{"input":"Target: [0, 10], Intervals: [0, 3], [2, 5], [4, 7], [6, 9], [8, 10]","title":"Interval Range Covering Example","output":"Minimum intervals: {[0, 3], [2, 5], [4, 7], [6, 9], [8, 10]} — 5 intervals needed","description":"Finding minimum intervals to cover target [0, 10]","explanation":"These 5 intervals chain together with overlapping coverage: [0,3] → [2,5] → [4,7] → [6,9] → [8,10]. Each overlap ensures no gap exists. Alternative: {[0, 3], [2, 7], [6, 10]} if those intervals existed would need only 3."},"type":"example"},{"data":{"content":"**The Greedy Strategy: Extend Furthest**\n\nThe greedy algorithm uses a \"furthest reach\" strategy:\n\n1. **Sort intervals by starting point**\n2. **Initialize** current position at `T_start`, count = 0\n3. **While** current position < `T_end`:\n - Among all intervals that **start at or before** current position, find the one that **ends furthest**\n - If no such interval exists (gap!), return impossible\n - Select this interval, update current position to its end, increment count\n4. **Return** count (or the list of selected intervals)\n\nThe key insight: at each step, we want to advance as far as possible while maintaining coverage continuity. The interval starting earliest but reaching furthest achieves this."},"type":"text"},{"data":{"fileName":"range_covering.py","languages":[{"code":"$6e","label":"Python","value":"python"},{"code":"$6f","label":"TypeScript","value":"typescript"}]},"type":"code"}],"titleType":"number","titleNumber":4},{"id":"range-covering-proof","title":"Correctness Proof for Range Covering","content":[{"data":{"content":"$70"},"type":"text"},{"data":{"icon":"Lightbulb","title":"Why Sorting by Start Time?","content":"Unlike interval stabbing (sort by end), range covering sorts by START. The reason: we iteratively extend from a current position, so we need efficient access to 'all intervals that could continue from here'—those starting at or before our current position. Sorting by start lets us sweep through candidates efficiently.","variant":"tip"},"type":"callout"},{"data":{"rows":[["Input","Set of intervals","Set of intervals + target range"],["Output","Points that pierce all intervals","Intervals that cover the target"],["Sort by","End time","Start time"],["Greedy choice","Place point at right endpoint","Select interval with furthest reach"],["Key insight","Delay point placement as long as possible","Extend coverage as far as possible"],["Failure mode","N/A (always possible)","Gap in coverage (impossible)"]],"caption":"Comparing the Two Covering Problems","headers":["Aspect","Interval Stabbing","Range Covering"]},"type":"table"}],"titleType":"number","titleNumber":5},{"id":"variations-extensions","title":"Variations and Extensions","content":[{"data":{"content":"Both covering problems have important variations that appear in practice and interviews:\n\n**1. Weighted Interval Covering**\n\nWhat if each interval has a cost/weight, and we want to minimize total cost rather than count? This becomes harder—greedy no longer works directly, and we typically need dynamic programming or even more sophisticated algorithms.\n\n**2. K-Coverage**\n\nInstead of covering each point once, cover each point at least `k` times. This requires tracking \"coverage depth\" and changes the algorithm significantly.\n\n**3. Circular Intervals**\n\nWhen intervals wrap around (like hours on a clock), we may need to try different \"break points\" and apply the linear algorithm multiple times.\n\n**4. Minimum Intervals for K-Disjoint Coverage**\n\nSelect minimum intervals such that the target is covered AND selected intervals form groups of size at most `k`. This introduces combinatorial constraints."},"type":"text"},{"data":{"items":["**Video Surveillance** — Minimum cameras to cover all hallways (intervals = camera coverage ranges)","**Satellite Communication** — Minimum ground stations to maintain continuous contact with an orbiting satellite","**Pipeline Inspection** — Minimum sensor placements along a pipeline route","**Broadcasting** — Minimum transmitters to cover a highway or rail line","**Shift Scheduling** — Minimum workers to cover all required operating hours"],"title":{"icon":"Target","text":"Real-World Applications","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"icon":"AlertCircle","title":"When Greedy Fails: Weighted Covering","content":"If intervals have different costs, greedy by 'furthest reach' may miss cheaper combinations. Example: Target [0, 10], Interval A = [0, 10] costs 100, Intervals B = [0, 5] and C = [5, 10] each cost 10. Greedy picks A (one interval, cost 100), but B+C (two intervals, cost 20) is cheaper. Weighted covering requires DP.","variant":"warning"},"type":"callout"}],"titleType":"number","titleNumber":6},{"id":"implementation-insights","title":"Implementation Insights and Edge Cases","content":[{"data":{"content":"When implementing covering algorithms, several subtleties require attention:\n\n**Edge Cases for Interval Stabbing:**\n\n1. **Empty input** — Return empty point set (0 points needed)\n2. **Single interval** — One point at its endpoint suffices\n3. **All intervals share a common point** — Only one point needed\n4. **No overlap between any pair** — Need as many points as intervals\n5. **Open vs closed intervals** — Must decide if endpoints are included (`[a, b]` vs `(a, b)`)\n\n**Edge Cases for Range Covering:**\n\n1. **Target is empty** (start ≥ end) — Zero intervals needed\n2. **No interval starts at or before target start** — Impossible\n3. **Gap in the middle** — Detected when no valid extension exists\n4. **Target exactly matches one interval** — One interval suffices\n5. **Floating point coordinates** — Use appropriate comparison tolerance"},"type":"text"},{"data":{"fileName":"edge_cases.py","languages":[{"code":"$71","label":"Python","value":"python"}]},"type":"code"},{"data":{"icon":"Lightbulb","title":"Debugging Covering Algorithms","content":"When your algorithm gives wrong answers, visualize the intervals on a number line. Mark the points or selected intervals. Check: (1) Did sorting work correctly? (2) At each step, did you consider ALL valid candidates? (3) For range covering, did you update the current position correctly after each selection?","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":7},{"id":"summary","title":"Summary: Interval Covering Mastery","content":[{"data":{"content":"Interval covering represents the \"flip side\" of interval selection—instead of avoiding overlap, we embrace it to achieve complete coverage. The two core problems and their greedy solutions form essential tools in your algorithm toolkit."},"type":"text"},{"data":{"type":"ordered","items":["**Interval Stabbing (Minimum Points)** — Sort by END time, place points at right endpoints, skip covered intervals. O(n log n) time.","**Range Covering (Minimum Intervals)** — Sort by START time, greedily select the interval with furthest reach at each step. O(n log n) time.","**Proof technique** — Both use the exchange argument, showing greedy choices can replace optimal choices without increasing cost.","**Covering vs. Packing duality** — Activity selection maximizes non-overlapping count; covering minimizes resources for complete coverage.","**Weighted variants are harder** — When costs differ, greedy fails; DP or other techniques required."],"title":{"icon":"CheckCircle","text":"Key Takeaways","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"content":"**Coming Up Next:**\n\nWe've covered the \"single-resource\" perspective on intervals. But what if multiple activities can occur simultaneously, each requiring its own resource? The **Meeting Rooms problem** asks: how many resources (rooms, platforms, processors) do we need to handle all intervals without conflict? This leads us into a new dimension of interval scheduling."},"type":"text"},{"data":{"icon":"CheckCircle","title":"Page Complete","content":"You now understand the covering perspective on interval scheduling. You can solve minimum point stabbing, minimum interval covering, prove these algorithms correct, and recognize when greedy applies. Next, we explore meeting room problems—determining resource requirements for overlapping intervals.","variant":"success"},"type":"callout"}],"titleType":"number","titleNumber":8}],"isLocked":false},{"id":"seed_f6eee3d27c52479e47983ae420550f6f","title":"Meeting Rooms Problems","order":1,"content":null,"isLocked":true},{"id":"seed_3419b33ab85ea4f3c932d95496a8eada","title":"Minimum Platforms / Resources","order":2,"content":null,"isLocked":true},{"id":"seed_f8a71a1c650e428a8e793ad0cb6511d4","title":"Event-Based Sweeping","order":3,"content":null,"isLocked":true}]}}