Solução Informática Iniciante – Semana 50 – Problema 1

Solução por Lúcio Cardoso

Vamos descobrir o primeiro capítulo que não foi lido totalmente, ou seja, o capítulo que contém a página $$k$$. Se o capítulo $$i$$ contém a página $$k$$, então $$l_i \leq k$$ e $$k \leq r_i$$, ou seja, $$k$$ está entre $$l_i$$ e $$r_i$$. Assim, para encontrar o primeiro capítulo não lido, basta testar a condição acima em cada um dos capítulos e quando for verdadeira, guardamos o índice do capítulo em uma variável $$ind$$. Assim, a resposta será $$N-ind+1$$ (quantidade de capítulos desde $$ind$$ até $$N$$). A complexidade será então $$O(n)$$.

Confira o código abaixo para melhor entendimento:
https://gist.github.com/luciocf/d8c7a2cb914374301cee90adc82a13f5