Algorithm
Problem Name: 2 AD-HOC - beecrowd | 2387
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2387
Dentista
Por OBI - Olimpíada Brasileira de Informática 2010 
Brazil
Timelimit: 1
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.
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.
| Exemplos de Entrada | Exemplos de Saída |
|
3 10 100 40 130 120 200 |
2 |
Code Examples
#1 Code Example with C Programming
Code -
C Programming
typedef struct consulta{
unsigned iniConsulta;
unsigned fimConsulta;
} consulta;
#include <stdio.h>
#include <stdlib.h>
int compara(const void *a, const void *b);
int main (void)
{
unsigned qtsConsultas;
unsigned qtsConsultasMax = 1;
unsigned i, j;
scanf("%u", &qtsConsultas);
// Vetor de struct;
consulta agenda[qtsConsultas];
for (i = 0; i < qtsConsultas; i++)
scanf("%u %u", &agenda[i].iniConsulta, &agenda[i].fimConsulta);
j = 0;
// Ordena o vetor de struct em ordem crescente pelo campo "fimConsulta";
qsort(agenda, qtsConsultas, sizeof(consulta), compara);
// Se um inicio de consulta for maior ou igual ao fim de consulta, quer dizer
// Que os horários não se sobrepoem;
// 'j' recebe o valor de i e se torna a nova consulta atual;
for (i = 1; i < qtsConsultas; i++)
{
if (agenda[i].iniConsulta >= agenda[j].fimConsulta)
{
qtsConsultasMax++;
j = i;
}
}
printf("%u\n", qtsConsultasMax);
}
// Função de comparação para o qsort;
int compara(const void *a, const void *b)
{
if ((*(struct consulta*)a).fimConsulta == (*(struct consulta*)b).fimConsulta)
return 0;
else if ((*(struct consulta*)a).fimConsulta > (*(struct consulta*)b).fimConsulta)
return 1;
else
return -1;
}
Input
10 100
40 130
120 200
Output
#2 Code Example with C++ Programming
Code -
C++ Programming
#include <algorithm>
#include <cstdio>
#include <deque>
using namespace std;
int main() {
int n, resposta = 0, momento = 0;
deque < pair<int, int> > fila;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
int inicio, termino;
scanf("%d %d", &inicio, &termino);
fila.push_back(make_pair(termino, inicio));
}
sort(fila.begin(), fila.end());
while (!fila.empty()) {
pair < int, int> davez = fila.front();
fila.pop_front();
if (davez.second >= momento) {
momento = davez.first;
resposta++;
}
}
printf("%d\n", resposta);
return 0;
}
Input
10 100
40 130
120 200
Output