import copy


def greedy_cow_transport(cows,limit=10):
    """
    Uses a greedy heuristic to determine an allocation of cows that attempts to
    minimize the number of spaceship trips needed to transport all the cows. The
    returned allocation of cows may or may not be optimal.
    The greedy heuristic should follow the following method:

    1. As long as the current trip can fit another cow, add the largest cow that will fit
        to the trip
    2. Once the trip is full, begin a new trip to transport the remaining cows

    Does not mutate the given dictionary of cows.

    Parameters:
    cows - a dictionary of name (string), weight (int) pairs
    limit - weight limit of the spaceship (an int)

    Returns:
    A list of lists, with each inner list containing the names of cows
    transported on a particular trip and the overall list containing all the
    trips
    """
    consider_cows = copy.deepcopy(cows)
    transport_cows = []

    # O(n) + O(n) + O(n) + O(n) + O(1) = O(n)
    def get_cow_trip(trip_cows, limit):
        trip_limit = limit
        trip_transport = []
        # O(n)
        pick_cow = max(consider_cows.values())
        smallest_cow = min(consider_cows.values())

        # O(n) + O(1)
        for cow in trip_cows:
            if (pick_cow == cow[1] and trip_limit >= pick_cow) or (trip_limit >= cow[1]):
                trip_limit -= cow[1]
                trip_transport.append(cow[0])
                consider_cows.pop(cow[0])

            elif smallest_cow > trip_limit:
                break
        return trip_transport

    while consider_cows:
        # O(log(n)) + (nlog(n)) = O(nlog(n))
        trip = get_cow_trip(sorted(consider_cows.items(), key=lambda x: -x[1]), limit)
        transport_cows.append(trip)

    # O(nlog(n))
    return transport_cows