0695-guloso

# yaml-language-server: $schema=https://api.mundodocodigo.com.br/api/public/json/wok-problem.json --- version: '1.0' id: 695 name: Guloso origin: ufma slug: guloso authorSlugEditorial: alessio authorSlugProblem: leo-jales description: Márcio arrumou N mulheres em uma balada e precisa calcular seu desempenho. O objetivo é determinar o maior período contínuo em que ele esteve ocupado e o maior intervalo de descanso entre suas atividades. editorial: Para resolver este problema de processamento de intervalos, primeiro ordene todos os encontros pelo horário de início. Utilize uma abordagem gulosa para mesclar intervalos que se sobrepõem ou são adjacentes. Mantenha o horário de término do bloco atual e, ao encontrar um novo intervalo que comece após esse término, calcule o tempo de descanso decorrido e inicie um novo bloco de ocupação. O maior bloco e o maior descanso registrados serão a resposta final. successmsg: Parabéns! Você resolveu o problema com uma estratégia gulosa eficiente e ajudou o Márcio a organizar sua agenda de balada! difficultyLevelId: C timeComplexity: O(N logN) memoryLimitMb: 256 timeLimitSegs: 2.0 defaultStatement: a_pt_guloso skills: - algoritmo-guloso - lacos - basic-logic - vetores statements: - id: a-guloso testScenarioLevel: A thematicSkills: - points: 1 skill: daily-life testScenarios: - id: d-sample name: Caso Exemplo description: Valida a lógica básica com o exemplo fornecido no enunciado. helpTip: Verifique se você está ordenando os intervalos pelo horário de início antes de processar. level: D testType: TDD skills: - skill: entrada-saida points: 1 - skill: basic-programer points: 1 - id: a-performance-load name: Teste de Performance e Carga description: Testa a eficiência do algoritmo com o volume máximo de 100.000 intervalos e dados diversos. helpTip: Seu algoritmo está demorando muito? Verifique se a complexidade é O(N log N). level: A testType: TDD skills: - skill: complexity-analysis points: 1 - skill: sorting-searching points: 1 - id: a-adjacent-merge name: Mesclagem Adjacente description: 'Intervalos que terminam exatamente onde o próximo começa (ex: 100-200, 200-300).' helpTip: 'Lembre-se: se um encontro começa exatamente no fim do outro, eles fazem parte do mesmo período de ocupação.' level: A testType: TDD skills: - skill: algoritmo-guloso points: 1 - skill: selecao points: 1 - id: a-complete-overlap name: Sobreposição Total description: Vários intervalos pequenos contidos dentro de um único intervalo grande. helpTip: Ao mesclar, o fim do bloco atual deve ser o máximo entre o fim atual e o fim do novo intervalo. level: A testType: TDD skills: - skill: algoritmo-guloso points: 1 - skill: selecao points: 1 - id: a-zero-overlap name: Sem Sobreposição description: Intervalos totalmente desconexos com grandes períodos de descanso. helpTip: Certifique-se de calcular corretamente a diferença entre o fim de um bloco e o início do próximo. level: A testType: TDD skills: - skill: lacos points: 1 - skill: algoritmo-guloso points: 1 - id: b-all-identical name: Intervalos Idênticos description: Múltiplos intervalos exatamente iguais informados na entrada. helpTip: O algoritmo deve ser robusto o suficiente para tratar entradas duplicadas. level: B testType: TDD skills: - skill: basic-programer points: 1 - id: b-one-interval name: Único Intervalo description: Caso mínimo com apenas um intervalo de tempo. helpTip: Com apenas um intervalo, o tempo de descanso máximo deve ser zero. level: B testType: TDD skills: - skill: if-simple points: 1 - id: c-reverse-sorted name: Entrada Invertida description: Intervalos fornecidos em ordem decrescente de horário de início. helpTip: Não confie na ordem da entrada; a ordenação inicial é obrigatória. level: C testType: TDD skills: - skill: ordenacao points: 1 solutions: - id: a-optimal name: Solução Ótima description: Solução eficiente O(N log N) utilizando ordenação e uma única passagem para mesclagem de intervalos. level: A implementations: - filenames: - solution.cpp language: cpp paradigm: Imperative - filenames: - solution.java language: java paradigm: Imperative main: Main - filenames: - solution.py language: py paradigm: Imperative - filenames: - resolution.cpp language: cpp paradigm: Imperative - filenames: - resolution-2.cpp language: cpp paradigm: Imperative - id: b-brute-force name: Solução Sub-ótima description: Solução sub-ótima O(N^2) que realiza a mesclagem de intervalos de forma ingênua e lenta. level: B implementations: - filenames: - solution.py language: py paradigm: Imperative