글 읽기 - 반례좀 찾아주세요..

rudtn1406 4년 전 0

질문게시판 다 돌면서 반례 다 돌려봤는데 어디가 틀렸는지 모르겠네요 ㅠㅠ

#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;

class Time {
public:
	int start;
	int end;
	bool operator<(Time& t) {
		if (start == t.start) return end < t.end;
		else return start < t.start;
	}
};
Time arr[100001];
vector<Time> v;

int main()
{
	int N;
	scanf("%d", &N);

	for (int i = 0; i < N; i++)
		scanf("%d %d", &arr[i].start, &arr[i].end);

	sort(arr, arr + N);

	v.push_back(arr[0]);

	for (int i = 1; i < N; i++) {
		if (v[v.size() - 1].start == arr[i].start && v[v.size()-1].end != arr[i].start) continue;
		else v.push_back(arr[i]);
	}

	int maximum = 0;

	for (int i = 0; i < v.size(); i++) {
		int temp = 1;
		Time tT = v[i];
		for (int j = i+ 1; j < v.size(); j++) {
			if (tT.end > v[j].start)continue;
			else {
				tT = v[j];
				temp++;
			}
		}
		maximum = max(maximum, temp);
	}


	printf("%d", maximum);
}

oree2113 4년 전 1

반례입니다만.. 고쳐도 시간복잡도가 O(N²) 라서 시간 초과가 날 것같네요

4
1 2
3 10
4 5
6 7

// Answer : 3
// Output : 2

rudtn1406 4년 전 0

반례 덕분에 솔팅 방식 바꿔서 완료했습니다. 감사합니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례좀 찾아주세요..

rudtn1406 4년 전 0

oree2113 4년 전 1

rudtn1406 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말