Editing 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 &les; N &les; 100 000
*-1 400 000 000 &les; Ai < Bi &les; 1 400 000 000
*2 &les; P &les; N
*Două intervale se intersectează dacă au cel puţin un punct comun
*Pentru 30% dintre teste N &les; 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
<br>
== Exemplu 2 ==
;intervale3in.txt
:-1 0 0
;intervale3out.txt
: Nu au fost respectate cerintele impuse
<br>
== Rezolvare ==
<syntaxhighlight lang="python" line>
#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>