[C++] [CSES] Movie Festival (Sorting and Searching)

CSES Sorting and Searching 여섯번째 문제입니다.

그리디 문제에서 잘 알려진 scheduling 문제입니다.

문제를 풀다보면 10만 ~ 20만개의 입력이 들어온다면 무조건 O(NlogN) 안에 돌아야 하니 정렬을 항상 생각해보는 습관이 든 것 같습니다.

 

Task

 

In a movie festival n movies will be shown. You know the starting and ending time of each movie. What is the maximum number of movies you can watch entirely?

Input

The first input line has an integer n: the number of movies.

After this, there are n lines that describe the movies. Each line has two integers a and b: the starting and ending times of a movie.

Output

Print one integer: the maximum number of movies.

Constraints

• 1≤n≤2⋅1e5
• 1≤a<b≤1e9

Example

Input:
3
3 5
4 9
5 8

Output:
2

 

Code

#include<bits/stdc++.h>
using namespace std;

int n, s, e, ans = 1;
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin >> n;
    vector<pair<int, int>> v;
    for (int i=0;i<n;i++){
        cin >> s >> e;
        v.push_back({e, s});
    }
    sort(v.begin(), v.end());
    int cur = v[0].first;
    for (int i=1;i<n;i++){
        if (cur <= v[i].second){
            ans++;
            cur = v[i].first;
        }
    }
    cout << ans;
}

생각해야 하는 것

• 끝나는 시간의 오름차순으로 vector<pair<int, int>>를 정렬합니다. 저는 cmp 함수를 만들지 않아보았습니다.
• 이렇게 정렬된 배열을 처음부터 돕니다.
• 다음 인덱스 pair의 시작하는 시간이 현재 끝나는 시간 이후라면 ans를 1 늘려줍니다.
• 끝나는 시간 이전이라면 아무것도 하지 않고 다음 인덱스를 살펴봅니다. 그냥 넘어가는 이유는 두 스케줄이 겹친다는 의미이기 때문에 ans를 증가시키지 않는 것이고, cur의 값은 같은 ans안에서 항상 가장 작은 값을 유지해야 되기 때문입니다. 우리는 끝시간 기준으로 정렬했기 때문에 cur을 업데이트하지 않는 것이 가장 작은 값을 유지하는 방법입니다.