a4.py

import math
import operator


def main():
    """ 
    Description
    :raises:

    :rtype:
    """
    # arr = [(2, 4, 3), (3, 6, 1), (3, 5, 5),
    #        (5, 8, 2), (6, 10, 5), (7, 10, 1), (14, 14, 1)]

    arr = [(2, 4, 3), (3, 6, 1), (3, 5, 5),
           (5, 8, 2), (6, 12, 5), (7, 10, 1), (14, 14, 1)]

    expected_out = [arr[0], arr[1], arr[3], arr[5], arr[6]]

    print("original", arr)
    res = cakes(arr, 0, len(arr) - 1)
    res.sort(key=operator.itemgetter(0))

    print("out", res)
    print("expected", expected_out)

    if len(res) == len(expected_out):
        ok = True
        for i in range(0, len(res)):
            if res[i] != expected_out[i]:
                print('wrong')
                ok = False
                break
        if ok:
            print('ok')
    else:
        print('wrong')


def cakes(arr, start, end):
    if start == end:
        result = [arr[start]]
        return result

    mid = (start + end) // 2

    a1 = cakes(arr, start, mid)
    a2 = cakes(arr, mid + 1, end)

    result = merge(a1, a2)

    return result


def merge(a1, a2):
    result = []
    i = 0  # to access elements in a1
    j = 0  # to access elements in a2

    while i < len(a1) and j < len(a2):
        (l_i, r_i, z_i) = a1[i]
        (l_j, r_j, z_j) = a2[j]

        if l_i < l_j:
            if z_i > z_j:
                result.append(a2[j])
                j += 1
            result.append(a1[i])
            i += 1
        elif l_i == l_j:
            if z_i < z_j:
                result.append(a1[i])
                i += 1
            else:
                result.append(a2[j])
                j += 1
        else:
            result.append(a2[j])
            j += 1

    return result


if __name__ == "__main__":
    main()