0699 - Intervale3

Enunt

Se consideră N intervale [Ai,Bi], 1 ≤ i ≤ N disjuncte.

Tuturor intervalelor li se aplică o operație de extindere la ambele capete cu o valoare naturală x, astfel încât după extindere cu valoarea x, intervalul [Ai,Bi] va deveni intervalul [Ai-x,Bi+x], 1 ≤ i ≤ N.

După extindere, spunem că intervalele [Ai,Bi] și [Aj,Bj] aparțin aceluiași grup de intervale dacă ele se intersectează sau dacă există un interval [Ak,Bk] astfel încât [Ai,Bi] se intersectează cu [Ak,Bk] iar intervalele [Ak,Bk], [Aj,Bj] aparțin aceluiași grup de intervale.

Cerința

Să se determine valoarea minimă x cu care vor trebui să fie extinse toate intervalele astfel încât să se formeze un grup cu cel puțin P intervale.

Date de intrare

Fișierul de intrare intervale3in.txt conține pe prima linie numerele naturale N și P cu semnificația din enunț. Pe următoarele N linii sunt descrise cele N intervale, câte un interval pe linie. Pentru fiecare interval i sunt specificate capetele sale Ai şi Bi.

Date de ieșire

Fișierul de ieșire intervale3out.txt va conţine pe prima linie numărul natural x ce reprezintă valoarea minimă cu care vor trebui extinse intervalele astfel încât să se obțină cel puțin un grup format din cel minimum P intervale.

Restricții și precizări

• 2 ⩽ N ⩽ 100 000
• -1 400 000 000 ⩽ Ai < Bi ⩽ 1 400 000 000
• 2 ⩽ P ⩽ N
• Două intervale se intersectează dacă au cel puţin un punct comun
• Pentru 30% dintre teste N ⩽ 10 000

Exemplu 1

intervale3in.txt

7 3

8 9

21 25

14 17

1 4

28 32

35 42

100 200

intervale3out.txt

2

Exemplu 2

intervale3in.txt

-1 0 0

intervale3out.txt

Nu au fost respectate cerintele impuse

Rezolvare

<syntaxhighlight lang="python" line>

1. 0699 - Intervale3

def read_input(file_name):

   try:
       with open(file_name, 'r') as file:
           N, P = map(int, file.readline().split())
           intervals = [list(map(int, file.readline().split())) for _ in range(N)]

           return N, P, intervals
   except Exception as e:
       print(f"Nu au fost respectate cerintele impuse: {str(e)}")
       return None

def write_output(file_name, result):

   with open(file_name, 'w') as file:
       if result is not None:
           file.write(str(result) + "\n")

def min_extension(N, P, intervals):

   intervals.sort()

   left, right = 0, max(intervals[i][1] - intervals[i][0] for i in range(N))
   result = 2

   while left <= right:
       mid = (left + right) // 2
       groups = 1
       end = intervals[0][1]

       for i in range(1, N):
           if intervals[i][0] - mid <= end:
               end = max(end, intervals[i][1])
           else:
               groups += 1
               end = intervals[i][1]

       if groups >= P:
           result = min(result, mid)
           right = mid - 1
       else:
           left = mid + 1

   return result

def main(input_file, output_file):

   result = read_input(input_file)
   if result is not None:
       N, P, intervals = result
       result = min_extension(N, P, intervals)
       write_output(output_file, result)

if __name__ == "__main__":

   main("intervale3in.txt", "intervale3out.txt")

</syntaxhighlight>