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

#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")