그리디 알고리즘 — 최적의 선택이 전체 최적이 되는 조건

public static int activitySelection(int[][] activities) {
    // 종료 시간 기준 정렬
    Arrays.sort(activities, Comparator.comparingInt(a -> a[1]));

    int count = 1;
    int lastEnd = activities[0][1];

    for (int i = 1; i < activities.length; i++) {
        if (activities[i][0] >= lastEnd) { // 시작 시간 >= 이전 종료 시간
            count++;
            lastEnd = activities[i][1];
        }
    }
    return count;
}

public static int coinChange(int[] coins, int amount) {
    Arrays.sort(coins);
    int count = 0;

    for (int i = coins.length - 1; i >= 0; i--) {
        count += amount / coins[i];
        amount %= coins[i];
    }

    return amount == 0 ? count : -1; // 거슬러줄 수 없으면 -1
}

[500, 100, 50, 10]원 → 그리디 OK (배수 관계)
[1, 3, 4]원, 6원 → 그리디 실패!
  그리디: 4+1+1 = 3개
  최적:   3+3   = 2개 (DP 필요)

public static double fractionalKnapsack(int capacity, int[][] items) {
    // 무게 대비 가치(단가) 기준 정렬
    Arrays.sort(items, (a, b) ->
        Double.compare((double) b[1] / b[0], (double) a[1] / a[0])
    );

    double totalValue = 0;
    int remaining = capacity;

    for (int[] item : items) {
        int weight = item[0], value = item[1];

        if (remaining >= weight) {
            totalValue += value;
            remaining -= weight;
        } else {
            totalValue += (double) value / weight * remaining;
            break;
        }
    }
    return totalValue;
}

public static Map<Character, String> huffmanEncoding(Map<Character, Integer> freq) {
    // min-heap: 빈도가 낮은 노드부터
    PriorityQueue<int[]> pq = new PriorityQueue<>(
        Comparator.comparingInt(a -> a[0])
    );

    // 각 문자를 리프 노드로
    for (var entry : freq.entrySet()) {
        pq.offer(new int[]{entry.getValue(), entry.getKey()});
    }

    // 가장 빈도가 낮은 두 노드를 합치기를 반복
    while (pq.size() > 1) {
        int[] left = pq.poll();
        int[] right = pq.poll();
        pq.offer(new int[]{left[0] + right[0], -1}); // 내부 노드
    }

    // 트리를 순회하며 코드 할당 (실제 구현은 트리 구조 필요)
    return buildCodes(pq.poll());
}

1. 직감적으로 그리디 전략을 세운다
2. 작은 예제로 테스트한다
3. 반례가 있으면 DP로 전환한다
4. 반례가 없으면 증명을 시도한다 (교환 논증)

// 하나의 회의실에서 최대한 많은 회의 배정
// = 활동 선택 문제 → 종료 시간 정렬 + 그리디

// 모든 회의를 진행하기 위한 최소 회의실 수
public static int minMeetingRooms(int[][] intervals) {
    Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));

    PriorityQueue<Integer> endTimes = new PriorityQueue<>();

    for (int[] interval : intervals) {
        if (!endTimes.isEmpty() && endTimes.peek() <= interval[0]) {
            endTimes.poll(); // 기존 회의실 재사용
        }
        endTimes.offer(interval[1]); // 회의실 배정
    }

    return endTimes.size();
}

// Run-Length Encoding도 그리디의 일종
// "aaabbc" → "a3b2c1"