[BOJ] 겹치는 선분 - Compy's Blog

겹치는 선분

TimeLimit	MemoryLimit	Condition	TAG
2s	256MB	(1 ≤ N ≤ 1,000,000 \|e\| ≤ 10억)	Greedy, Sort

이 문제는 솔직히… 아쉬웠따. 뭔가 그 게시판을 들어갔다가 잘못 봐버리면서 접근을 이미 약간 힌트를 얻어서 거의 그 이후로 바로 풀었는데.. 나는 반례있는지 확인하러 들어간 것 뿐인데.. 쩝

하튼 그냥 정렬해서 잘 풀면 된다. 아이디어는 그렇게 어렵지도 완전 쉽지도 않은 아이디어였다.

시간에 대해서 어떻게 줄이지라고 고민을하면 약간 자연스럽게 접근할 수 있는 정도였다.

정답 코드

처음에 priority_queue로 풀고 있엇는데 이것도 되는 것 같다ㅏ. 근데 요게 더 효율적이다.

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

using ll = long long;
int n;


bool compare(pair<int, int> a, pair<int ,int> b){
    if(a.first == b.first) return a.second < b.second;
    return a.first < b.first;
}


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    cin >> n;
    
    int start, end;
    
    vector<pair<int, int>> coor;
    for(int i = 0; i < n; i++) {
        cin >> start >> end;
        
        coor.push_back({start, 1});
        coor.push_back({end, -1});
    }
    
    sort(coor.begin(), coor.end(), compare);
    
    int current = 0;
    int result = 0;
    for(int i = 0; i < n*2; i++){
//        cout << coor[i].first << " " <<coor[i].second << "\n";
        current += coor[i].second;
        result = max(result, current);
    }
    
    cout << result;
    
    
    return 0;
}