hackerlandRadioTransmitters.py

# source: https://www.hackerrank.com/challenges/hackerland-radio-transmitters

def hackerlandRadioTransmitters(houses, transmitter):
    houses.sort() # requires sorting => O(nlogn)
    transmitter_count = 0
    i = 0
    while i < len(houses): # O(n)
        transmitter_count += 1
        max_transmitting_house = houses[i] + transmitter
        # position after transmitting house
        while i < len(houses) and houses[i] <= max_transmitting_house:
            i += 1
            
        last_house = houses[i - 1] + transmitter
            
        while i < len(houses) and houses[i] <= last_house:
            i += 1
            
    return transmitter_count # Time complexity: O(nlogn + n) => O(nlogn)