Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

JDENTIST - Dentista

 

Os dentistas são extremamente meticulosos em seu trabalho, tendo que agir com muita precisão em todas as suas atividades. Pedro é um dentista meticuloso como todos os outros. Infelizmente sua secretária não é muito organizada e, com o intuito de ajudar sempre os pacientes, aceita que eles marquem consultas no horário que quiserem, sem se preocupar com os demais horários marcados, ocasionando vários coníitos de horários que muito incomodaram Pedro e os pacientes. Por exemplo, se uma consulta começar às 9 horas e durar 2 horas, nenhuma outra consulta deveria ser marcada para iniciar as 10 horas.

Ao perceber que sua agenda tinha coníito de horários, Pedro pediu sua ajuda para descobrir a maior quantidade de consultas que podem ser atendidas sem sobreposição.

Tarefa

Você deve escrever um programa que, dados os horários de início e término das consultas agendadas pela secretária, responda a quantidade máxima de consultas que podem ser atenditas sem sobreposição.

Entrada

A primeira linha da entrada contém um inteiro N (1 ≤ N ≤ 10.000) que indica quantas consultas a secretária marcou. Cada uma das N linhas seguintes contém um par de inteiros X e Y separados por um espaço em branco (0 ≤ X < Y ≤ 1.000.000) que representam, respectivamente, o horário de início e de término da consulta. Considere que se uma consulta inicia no exato instante em que outra termina não há sobreposição. Os horários de início são fornecidos em ordem, podendo haver mais de uma consulta que inicie no mesmo horário.

Saída

Seu programa deve imprimir uma única linha, contendo um inteiro que representa a quantidade máxima de consultas que podem ser atendidas sem que haja qualquer sobreposição.

Exemplo

Entrada
3
10 100
40 130
120 200

Saída
2

Entrada

4
10 20
20 30
30 40
40 50

Saída
4

Entrada
5
10 30
20 40
30 60
40 80
60 100

Saída
3


Adicionado por:Wanderley Guimarăes
Data:2011-04-06
Tempo limite:0.309s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP PERL6 PY_NBC SCALA TCL
Origem:OBI 2010 - Fase 2 nível junior

hide comments
2017-12-19 06:25:30
A dica é "número MÁXIMO", da pra fazer em O(logN).

Last edit: 2017-12-19 06:26:54
2016-04-06 06:36:52 Elsio [UFABC]
Semelhante ao SORVETE (obi) do spoj
2016-04-02 18:55:38 Elsio [UFABC]
Esse pdf te mostra em uma das imagens tudo que vc precisa entender sobre esse problema http://www.each.usp.br/digiampietri/SIN5013/13-algoritmosGulosos.pdf
2013-02-19 16:20:54 Deryk Sedlak [UEL]
Pessoal que está com o problema de "resposta errada", tenta executar o seguinte teste:

4
10 25
25 30
25 30
25 30
-------
2

Espero ter ajudado alguém =) abraços.

Last edit: 2013-02-19 16:22:27
2013-02-19 15:53:33 Deryk Sedlak [UEL]


Last edit: 2013-02-19 16:21:41
2013-02-06 12:46:34 Ruan Pablo Medeiros
porque teria que dar 2 o resultado rafael?
2012-10-31 19:48:29 Luiz Antonio Avanzi Junior [UNISO]
Pessoal, o meu tbm "parecia" estar tudo certo, mas ao ver este caso de teste:
8
10 40
11 50
13 35
14 60
15 30
16 50
30 40
45 50
-------
3

Percebi que precisa fazer uma ordenaçăo do vetores Y, pra depois fazer as comparaçőes e incrementar a variável consulta... =)
Espero ter ajudado...
flws..
2012-10-29 11:14:21 Phellipe Gonzaga
Alguem poderia me envia a solucao do problema do dentista para ver onde o meu esta dando erro....
phellipegonzaga@gmail.com
Ficarei grato
att...!!
2011-08-07 00:32:23 GNU [UFPB]
Uma dica seria usar a biblioteca STL do C++ e fazer um vetor<pair<int,int>> v;
E sair comparando o primeiro com o segundo. Pra saber se é maior que o outro se for incrementa-o. Fica a dica!
kevinmitinick@hotmail.com

Last edit: 2011-08-07 00:34:32
2011-06-25 20:32:12 Alan
Tive o mesmo problema. Passei por todos os casos de teste e nada.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.