BOJ(백준) 2283번 구간 자르기

https://www.acmicpc.net/problem/2283

2283번: 구간 자르기

스위핑(imos), 누적합, 투포인터 세가지 알고리즘이 잘 섞여있는 좋은 문제이다. 

 

문제를 푸는 순서는 다음과 같다.

① imos 알고리즘을 사용해 0부터 1,000,000까지 좌표에서 지나가는 선의 개수를 배열에 저장한다.

② 해당 배열의 누적합을 구한다.

③ 투포인터를 사용해 제일 먼저 조건을 만족하는 구간을 찾는다.

 

AC code

#include <bits/stdc++.h>
using namespace std;
int N,K,t1,t2,arr[1000001],cnt;
vector<pair<int,int>> v;

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>N>>K;
	for(int i=0;i<N;i++) {
		cin>>t1>>t2;
		v.push_back({t1,1});
		v.push_back({t2,-1});
	}
	sort(v.begin(),v.end());
	for(int i=0,k=0;i<=1000000;i++) {
		arr[i]=cnt;
		if(i) arr[i]+=arr[i-1];
		while(k<v.size()&&v[k].first==i) cnt+=v[k++].second;
	}
	for(int i=0,k=0;k<=1000000;) {
		int diff=arr[k]-arr[i];
		if(diff==K) {
			cout<<i<<" "<<k;
			return 0;
		}
		if(diff<=K) k++;
		else i++;
	}
	cout<<"0 0";
}