def satisfying_booking(R):
    '''
    Input:  R | Tuple of |R| talk request tuples (s, t)
    Output: B | Tuple of room booking triples (k, s, t)
              | that is the booking schedule that satisfies R
    '''
    B = []
    times = []
    for r in R:
        times.append((r[0],1))
        times.append((r[1],-1))
    times.sort()

    bookings = []
    rooms = 0
    current_time = times[0][0]
    prev_time = times[0][0]
    for i in range(len(times)):
        current_time = times[i][0]
        if current_time == prev_time:
            rooms += times[i][1]
        elif current_time != prev_time:
            bookings.append((prev_time, rooms))
            rooms += times[i][1]
        prev_time = current_time

    bookings.append((times[-1][0], rooms))

    previous_number_of_rooms = 1
    number_of_rooms = 1
    start_time = None

    for bk in bookings:
        if start_time == None:
            start_time = bk[0]
        number_of_rooms = bk[1]
        if number_of_rooms != previous_number_of_rooms:
            if previous_number_of_rooms != 0:
                B.append((previous_number_of_rooms,start_time, bk[0]))
            start_time = bk[0]
        previous_number_of_rooms = number_of_rooms

    return B