Greedy Algorithms and Intervals

# CHAPTER 16

Greedy Algorithms and Intervals #

1. Chapter Introduction #

2. What makes an Algorithm "Greedy"? #

• Take 25c (Remainder: 40c).

• Take 25c (Remainder: 15c).

• Take 10c (Remainder: 5c).

• Take 5c (Remainder: 0c).

3. Pattern 1: Activity Selection / Scheduling #

def maxMeetings(meetings):
    # Sort meetings by their END time: x[1]
    meetings.sort(key=lambda x: x[1])
    
    count = 0
    last_end_time = -1
    
    for start, end in meetings:
        if start >= last_end_time:
            # We can attend this meeting!
            count += 1
            last_end_time = end # Update schedule
            
    return count
# Time: O(N log N) due to sorting, Space: O(1)

4. Pattern 2: Merge Intervals #

*The Strategy:* Sort by Start Time.

1. 1. Sort the array based on the start value of each interval.

1. 2. Initialize a merged list with the first interval.

1. 3. Iterate through the remaining intervals.

1. 4. If the start of the current interval is LESS THAN OR EQUAL TO the end of the last interval in merged, they overlap!

1. 5. Update the end of the last interval in merged to be the max() of both ends.

public int[][] merge(int[][] intervals) {
    if (intervals.length <= 1) return intervals;
    
    // Sort by ascending starting point
    Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
    
    List<int[]> merged = new ArrayList<>();
    int[] currentInterval = intervals[0];
    merged.add(currentInterval);
    
    for (int[] interval : intervals) {
        int currentEnd = currentInterval[1];
        int nextStart = interval[0];
        int nextEnd = interval[1];
        
        if (currentEnd >= nextStart) {
            // Overlapping intervals, update the end if needed
            currentInterval[1] = Math.max(currentEnd, nextEnd);
        } else {
            // Disjoint interval, add it to the list and reassign current
            currentInterval = interval;
            merged.add(currentInterval);
        }
    }
    return merged.toArray(new int[merged.size()][]);
}
// Time: O(N log N)

5. Pattern 3: Insert Interval #

1. 1. Iterate. While current interval ends *before* the new interval starts, append it to the result.

1. 2. While current interval overlaps with the new interval, merge them by updating newInterval's start/end with the min() and max().

1. 3. Append the final merged newInterval.

1. 4. Append any remaining intervals.

6. The "Sorting" Prerequisite #

7. Real-World Scenario: CPU Task Scheduling #

8. Mini Project: Jump Game #

9. Common Mistakes #

• Assuming Greedy Always Works: Greedy algorithms are fast, but they don't look ahead. If a problem has complex interconnected constraints (like the Knapsack problem), a local optimal choice might trap you in a global sub-optimal result. Before writing code, mentally verify that the greedy choice holds true for edge cases.

10. Best Practices #

• Sorting Syntax: Be fluent in writing custom comparators for 2D arrays in your chosen language.

• Python: intervals.sort(key=lambda x: x[0])

• Java: Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

11. Exercises #

1. 1. Trace the Merge Intervals logic for [[1,4], [4,5]]. Do they overlap?

1. 2. In the maxMeetings problem, why do we sort by *end* time rather than *start* time?

12. MCQs #

14. Interview Questions #

• Q: "Given an array of meeting time intervals intervals where intervals[i] = [starti, endi], return the minimum number of conference rooms required." (LeetCode 253. Hint: Use a Min-Heap to track room end times).

15. FAQs #

• Q: How do I know if I should use Greedy or DP?

16. Summary #

17. Next Chapter Recommendation #