Sejam $$a[i],b[i]$$ os vetores que representam o horário mínimo e máximo de chegada do aluno $$i$$, respectivamente, criamos um vetor $$v[i]$$, onde $$v[j] =$$ quantidade de aluno que podem chegar na casa de João no horário $$j$$, a partir dessa ideia, basta achar o máximo entre $$v[j], 1 \leq j \leq 100000$$, mas para achar esta quantidade basta percorrer para todos os $$i$$, e adicionar 1 em $$v[j]$$ para $$a[i] \leq j \leq b[i]$$, pois encontramos um aluno que pode chegar no horário $$v[j]$$. Segue o código:
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <bits/stdc++.h> | |
| using namespace std; | |
| int a[100100], b[100100], v[100100]; | |
| int main() { | |
| int n, ans = 0; | |
| cin >> n; | |
| for(int i = 0; i < n; i++){ | |
| cin >> a[i] >> b[i]; | |
| } | |
| for(int i = 0; i < n; i++){ | |
| for(int j = a[i]; j <= b[i]; j++){ | |
| v[j]++; | |
| } | |
| } | |
| for(int i = 1; i <= 100000; i++){ | |
| ans = max(ans, v[i]); | |
| } | |
| cout << ans << "\n"; | |
| return 0; | |
| } |
Comente