Greedy Algorithm Introduction

package io.thecodeforge.algorithms.greedy;

import java.util.*;

/**
 * Production-grade implementation of the Activity Selection Problem.
 * Time Complexity: O(N log N) due to sorting.
 */
public class IntervalScheduler {
    public static class Interval {
        int start, end;
        public Interval(int start, int end) { this.start = start; this.end = end; }
        @Override
        public String toString() { return "(" + start + ", " + end + ")"; }
    }

    public List<Interval> selectMaxActivities(List<Interval> intervals) {
        if (intervals == null || intervals.isEmpty()) return Collections.emptyList();

        // Greedy Choice: Sort by finish time
        intervals.sort(Comparator.comparingInt(a -> a.end));

        List<Interval> result = new ArrayList<>();
        Interval lastSelected = intervals.get(0);
        result.add(lastSelected);

        for (int i = 1; i < intervals.size(); i++) {
            Interval current = intervals.get(i);
            // If this activity starts after or when the last one ends, pick it
            if (current.start >= lastSelected.end) {
                result.add(current);
                lastSelected = current;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        IntervalScheduler scheduler = new IntervalScheduler();
        List<Interval> input = Arrays.asList(
            new Interval(1, 4), new Interval(3, 5), new Interval(0, 6), 
            new Interval(5, 7), new Interval(3, 8), new Interval(5, 9),
            new Interval(6, 10), new Interval(8, 11), new Interval(12, 16)
        );
        System.out.println("Selected intervals: " + scheduler.selectMaxActivities(new ArrayList<>(input)));
    }
}

-- io.thecodeforge.analytics
-- Tracking greedy vs optimal counts in a simulated environment
CREATE TABLE denominations (coin_val INT);
INSERT INTO denominations VALUES (1), (3), (4);

-- A simple query to show how many of the LARGEST coin greedy would take
-- for an amount of 6.
SELECT 
    6 AS target_amount,
    MAX(coin_val) AS greedy_first_pick,
    (6 / MAX(coin_val)) AS coins_taken,
    (6 % MAX(coin_val)) AS remainder_to_process
FROM denominations
WHERE coin_val <= 6;
-- This logic clearly shows greedy leaves a remainder of 2, requiring 2 more coins.

# io.thecodeforge.infrastructure
FROM eclipse-temurin:17-jdk-jammy
WORKDIR /app
COPY . /app
RUN javac io/thecodeforge/algorithms/greedy/IntervalScheduler.java
# Run with memory limits to test efficiency
CMD ["java", "-Xmx128m", "io.thecodeforge.algorithms.greedy.IntervalScheduler"]