글 읽기 - 강의실 시간초과 질문입니다.

alohajihwan 7년 전 0

min_element의 시간복잡도가 선형이라서 시간 초과가 나는 것인가요?

어떤 방식으로 접근해야 하는지 알려주세요...ㅠㅠ

#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<functional>
#include<map>
using namespace std;
#define INF 999999999
#define ll long long

int N;
pair<int, int> arr[100011];
int main()
{
	cin >> N;
	for (int i = 0; i < N; i++) {
		int t;
		scanf("%d%d%d", &t, &arr[i].first, &arr[i].second);
	}
	sort(arr, arr + N);
	//강의실에서 강의가 끝나는 시간 저장
	vector<int>ans;
	ans.push_back(arr[0].second);
	for (int i = 1; i < N; i++) {
		//가장 먼저 끝나는 강의 시간 : ans[d]
		int d = min_element(ans.begin(), ans.end()) - ans.begin();
		//i번째 강의 시작 시간 : arr[i].first
		if (ans[d] <= arr[i].first) {
			ans[d] = arr[i].second;
		}
		else ans.push_back(arr[i].second);
	}
	printf("%d\n", ans.size());
}

dlwodnsdl 7년 전 2

한달정도 되서 도움이 될지는 모르겠는데, 어떤 수업의 시작하는 시간과 끝나는 시간을 연결짓지말고 따로 정렬해보세요.

alohajihwan 7년 전 1

답변 감사합니다. 근데 그래도 감이 안잡히네요..ㅠㅠㅠㅠ강의 각각의 시작하는 시간과 끝나는 시간을 따로 정렬한다는 의미 인가요?

dlwodnsdl 7년 전 3

진행되고 있는 수업의 수를 각 수업이 아닌 시간의 흐름에 따라서 어떻게 변화하는지를 고려하여 코딩을 하시면 시간 복잡도가 O(N)이 됩니다.

alohajihwan 7년 전 0

감사합니다!!! 좀더 고민해보겠습니다ㅎㅎㅎ

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

문제

문제

출처

ICPC

강의실 시간초과 질문입니다.

alohajihwan 7년 전 0

dlwodnsdl 7년 전 2

alohajihwan 7년 전 1

dlwodnsdl 7년 전 3

alohajihwan 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말