Boj 2283) 구간 자르기

Sweeping

백준 2283

설명

범위가 십만으로 얼마 안커서 배열에 다 저장해 일일히 노가다로 푸는 방식.

처음에 배열에서 이전 인덱스와의 차이만 넣어주면 다음 반복문에서 0부터 누적해서 한번에 원하는 값을 계산할 수 있음.

두개가 같을 때가 있는데 아무것도 선택 하지 않을 때임. while 문 조건에 p_r < p_l 이거 넣었다가 고생함.

시간 복잡도

O(1000001*3)

코드

#define MAXRANGE 1000003

int weights[MAXRANGE];

int main()
{
	int n, k;
	cin >> n >> k;
	int tmp1, tmp2;
	for (int i = 0; i < n; i++)
	{
		cin >> tmp1 >> tmp2;
		weights[tmp1]++; weights[tmp2]--;
	}
	
	for (int i = 0; i < MAXRANGE; i++)
		weights[i + 1] += weights[i];
	
	int sum = 0;
	int p_l=0, p_r = 0;
	
	while (p_r <= MAXRANGE && p_l <= p_r)
	{
		if (sum == k) {
			cout << p_l << " " << p_r << endl;
			return 0;
		}
		else if (sum < k)
			sum += weights[p_r++];
		else if(sum > k)	  
			sum -= weights[p_l++];
	}
	
	cout << 0 << " " << 0;
}