Határidő: 2022-04-27 24:00

Adott a számegyenesen \(N\) zárt intervallum, \([A_1, B_1], [A_2, B_2], \ldots [A_N, B_N]\), ahol \(A_i\) és \(B_i\) természetes számok. Szeretnénk meghatározni az intervallumok összhosszát, vagyis az \[\bigcup_{i = 1}^N [A_i, B_i]\] halmaz mértékét.

Az intervallum.py fájlban megadtunk egy példaprogramot, ami beolvassa az intervallumokat a parancssori argumentumban megadott nevű fájlból.

• A fájl minden sorában egy számpár, azaz egy szóközzel elválasztott két szám, \(A\) és \(B\) található, melyek megadják egy intervallum határait, ahol \(0 < A < B\).
• A read_intervals függvény a parancssorban megadott fájlból beolvasott számpárokból Interval objektumok listáját hozza létre. Az Interval osztálynak két tulajdonsága van, a start az intervallum kezdőpontja és end a végpontja.
• Egészítsük ki az measure függvényt úgy, hogy kiszámítsa az intervallumok összhosszát (mértékét)! Törekedjünk a hatékony, \(O(N \log N)\) lépésszámú megvalósításra.
• Próbáljuk ki a programot az alábbi bemeneteken. A hatékony, \(O(N \log N)\) lépésszámú algoritmus az alábbi bemenetek mindegyikén lefut néhány másodperc alatt. A bemenetek mellett ellenőrzésül megadtuk az intervallumok összhosszát is.

  Bemenet	Összhossz
  int1.text	9
  int2.text	596
  int3.text	6541
  int4.text	94581377
  int5.text	632741470