Greedy

그리디

지금의 선택이 전체에도 좋은지 판단해요

겹치지 않는 회의를 가장 많이 골라요

직전 회의 종료없어요

선택한 회의0

현재 위치비교 대상확인한 값

예제 코드

C++

#include <vector>#include <algorithm>#include <limits>#include <utility>int max_meetings(std::vector<std::pair<int, int>> intervals) {    std::sort(intervals.begin(), intervals.end(), [](auto a, auto b) {        if (a.second != b.second) {            return a.second < b.second;        }        return a.first < b.first;    });    int last_end = std::numeric_limits<int>::lowest();    int count = 0;    for (auto [start, end] : intervals) {        if (start >= last_end) {            last_end = end;            ++count;        } else {            continue;        }    }    return count;}

Python

def max_meetings(intervals):    intervals = sorted(        intervals,        key=lambda x: (x[1], x[0])    )    last_end = float("-inf")    count = 0    for start, end in intervals:        if start >= last_end:            last_end = end            count += 1        else:            continue    return count

시작하기

끝나는 시간순으로 정렬해요

겹치지 않는 회의를 가장 많이 골라요. 더 일찍 끝나는 회의를 선택하면 뒤에 남는 시간이 줄어들지 않아요.

사용 조건

겹치지 않는 회의를 가장 많이 고르는 예제예요. 종료 시간이 빠른 회의를 먼저 고르는 기준이 이 문제의 최적해를 보장해요.

먼저 알아두면 좋아요

정렬과 조건문을 알고 시작해요. 회의는 시작~종료 구간이며, 직전 회의가 끝나는 시각에 다음 회의를 시작할 수 있어요.

동작 원리

종료 시간이 빠른 순서로 정렬해요. 이전에 고른 회의와 겹치지 않으면 선택하고 마지막 종료 시간을 바꿔요.

더 일찍 끝나는 회의로 첫 선택을 바꿔도 뒤에 고를 수 있는 회의는 줄지 않아요. 이 성질을 반복해서 적용할 수 있어 이 문제에서는 그리디가 맞아요.

시간: O(n log n) · 정렬 후 n개 회의를 확인해요
추가 공간: O(n) · 이 예제는 정렬할 복사본을 만들어요

주의할 점

회의 길이가 가장 짧거나 시작 시간이 가장 빠르다는 기준은 이 문제의 정답을 보장하지 않아요.
그리디는 매번 큰 값을 고르는 방법이 아니에요. 선택 기준이 전체 최적해를 보장하는 이유가 필요해요.

직접 코드로 풀어봐요

배운 원리를 문제에 적용해요

C++ 실전 문제 보기 Python 실전 문제 보기

작성·운영 xhae123

MIT · 알고리즘 설계 강의

그리디