Ghisa Catalin: Pagină nouă: == Cerinţa == Dându-se '''N''' intervale '''[a, b]''', calculați numărul maxim de astfel de intervale care se intersectează în cel puțin un punct. == Date de intrare == Fișierul de intrare '''intervalein.txt''' conține pe prima linie numărul '''N''', iar pe următoarele '''N''' linii '''2''' numere naturale separate prin spații, reprezentând limitele intervalelor '''[a, b]'''. == Date de ieșire == Fișierul de ieșire '''intervaleout.txt''' va conține pe prima l...

2023-12-12T18:16:44Z

Pagină nouă: == Cerinţa == Dându-se '''N''' intervale '''[a, b]''', calculați numărul maxim de astfel de intervale care se intersectează în cel puțin un punct. == Date de intrare == Fișierul de intrare '''intervalein.txt''' conține pe prima linie numărul '''N''', iar pe următoarele '''N''' linii '''2''' numere naturale separate prin spații, reprezentând limitele intervalelor '''[a, b]'''. == Date de ieșire == Fișierul de ieșire '''intervaleout.txt''' va conține pe prima l...

New page

== Cerinţa ==
Dându-se '''N''' intervale '''[a, b]''', calculați numărul maxim de astfel de intervale care se intersectează în cel puțin un punct.
== Date de intrare ==
Fișierul de intrare '''intervalein.txt''' conține pe prima linie numărul '''N''', iar pe următoarele '''N''' linii '''2''' numere naturale separate prin spații, reprezentând limitele intervalelor '''[a, b]'''.
== Date de ieșire ==
Fișierul de ieșire '''intervaleout.txt''' va conține pe prima linie numărul '''mx''', reprezentând numărul maxim de intervale care se intersectează în cel puțin un punct.
== Restricţii şi precizări ==
* 1 &les; N &les; 100.000
* -2.000.000.000 &les; a &les; b &les; 2.000.000.000
== Exemplu ==
; intervalein.txt
5
1 5
3 4
-10 10
-23 -20
100 200
; intervaleout.txt
Datele de intrare corespund restrictiilor impuse.
3
<br>
== Exemplu 2 ==
; intervalein.txt
-1
1 5
3 4
-10 10
-23 -20
100 200
; intervaleout.txt
Datele de intrare nu corespund restrictiilor impuse.
<br>
== Rezolvare ==
<syntaxhighlight lang="python" line>
def max_intersecting(intervals):
# Sortăm intervalele după capătul drept
intervals.sort(key=lambda x: x[1])

# Inițializăm o listă pentru a stoca intervalele în curs de procesare
current_intervals = []

# Inițializăm numărul maxim de intervale care se intersectează
max_inter = 0

for interval in intervals:
# Adăugăm intervalul curent la lista de intervale în curs de procesare
current_intervals.append(interval)

# Eliminăm intervalele care s-au terminat
while current_intervals and current_intervals[0][1] < interval[0]:
current_intervals.pop(0)

# Actualizăm numărul maxim de intervale care se intersectează
max_inter = max(max_inter, len(current_intervals))

return max_inter

def main():
# Deschidem fișierul de intrare și citim datele
with open('intervalein.txt', 'r') as f:
n = int(f.readline().strip())
intervals = [list(map(int, f.readline().strip().split())) for _ in range(n)]

# Verificăm dacă numărul de intervale respectă restricțiile
if 1 <= n <= 100000 and all(-2000000000 <= a <= b <= 2000000000 for a, b in intervals):
# Dacă da, calculăm numărul maxim de intervale care se intersectează
result = max_intersecting(intervals)
status = "Datele de intrare corespund restrictiilor impuse."
else:
# Dacă nu, afișăm un mesaj de eroare
result = ""
status = "Datele de intrare nu corespund restrictiilor impuse."

# Scriem rezultatul în fișierul de ieșire
with open('intervaleout.txt', 'w') as f:
f.write(status + '\n' + str(result))

if __name__ == "__main__":
main()

</syntaxhighlight>

3975 - Intervale AB - Revision history