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.|

FOCO - Foco

Daniel está fazendo um curso de Visão Computacional e decidiu reproduzir um trabalho muito interessante visto em aula: ele tirou várias fotos de uma mesma cena, variando apenas o foco, para depois combiná-las em uma única imagem onde todos os objetos da cena estão nítidos simultaneamente. Para tal, ele precisa que cada objeto apareça nítido em ao menos uma foto.

Daniel sabe que, para cada objeto, existe um intervalo fechado de planos de foco no qual aquele objeto fica nítido. Por exemplo, na figura abaixo, (i), (ii) e (iii) são três fotos da mesma cena, cada uma tirada com um foco diferente; (iv) é a imagem combinada gerada por Daniel.

Como o cartão de memória de sua câmera é pequeno, ele pediu sua ajuda para, dados os intervalos de foco de todos os objetos da cena que pretende fotografar, determinar o número mínimo de fotos que ele deve tirar para que seja possível deixar cada objeto nítido em pelo menos uma foto.

Entrada

A entrada é composta por diversos casos de teste. A primeira linha de cada caso de teste contém um inteiro N indicando o número de objetos na cena. Cada uma das N linhas seguintes contém dois inteiros A e B indicando os extremos do intervalo de foco de cada objeto.

Saída

Para cada caso de teste, imprima uma linha contendo um inteiro indicando o menor número de fotos que Daniel deve tirar.

Restrições

  • 1 ≤ N ≤ 10⁶
  • 1 ≤ A ≤ B ≤ 10⁹
  • Exemplos

    Entrada
    
    3
    1 3
    2 5
    4 6
    5
    1 2
    5 6
    3 4
    5 6
    1 2
    
    Saída
    
    2
    3
    
    

    Adicionado por:Wanderley Guimarăes
    Data:2012-05-26
    Tempo limite:0.104s-0.452s
    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:Primeira fase da Maratona de Programação - 2011

    hide comments
    2013-03-05 07:50:50 william santos



    Last edit: 2013-03-05 08:28:20
    2012-06-05 02:43:06 Alessandro Menezes [UFC - Quixadá]
    Dica: para reduzir o tempo năo use cin, cout e endl do c++, use printf e scanf.

    Last edit: 2012-09-13 12:26:36
    2012-05-27 18:01:48 Alan Peixinho [UNESP]
    O tempo deste problema poderia ser aumentado, em python năo roda mesmo usando o psyco, e minha abordagem está em n*log(n)
    © Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.