Campus Bikes Ii - Leetcode Solution

Problem Statement:

You are given a list of n students and m bikes. Each student wants to be assigned to the nearest bike.

You are given two arrays:

1. An integer array students of length n where students[i] is the position of the ith student.
2. An integer array bikes of length m where bikes[j] is the position of the jth bike.

Write a function assignBikes(students: List[int], bikes: List[int]) -> List[int], that returns an integer array ans where:

• an[i] is the index (0-indexed) of the bike that the ith student is assigned to.

Each student is assigned to the bike that has the shortest distance from the student's position to the bike's position. If there are multiple bikes with the same shortest distance, we choose the bike with the smallest index. If there are multiple students assigned to the same bike, we choose the student with the smallest index.

Solution:

To solve this problem, we need to calculate the distance between each student and each bike. Then, for each student, we need to find the bike that is closest to him. We will use a priority queue to keep track of the closest bikes to each student.

We can calculate the distance between two points using the Euclidean distance formula: sqrt((x1-x2)^2 + (y1-y2)^2)

First, we will create a blank dictionary d and a blank priority queue q. We will iterate through all possible pairs of students and bikes, and calculate the distance between them. For each student, we will insert a tuple (distance, bike index, student index) into the priority queue.

from typing import List
import heapq

def assignBikes(students: List[int], bikes: List[int]) -> List[int]:
    # create blank dictionary
    d = {}
    # create blank priority queue
    q = []
    # iterate through all pairs of students and bikes
    for i in range(len(students)):
        for j in range(len(bikes)):
            # calculate distance between student i and bike j
            dist = abs(students[i]-bikes[j])
            # insert tuple into priority queue
            heapq.heappush(q, (dist, j, i))
    ans = [-1]*len(students)
    checkedBikes = set()
    # iterate through priority queue
    while q:
        # get bike with shortest distance to any student
        (dist, bike, student) = heapq.heappop(q)
        # if bike is not assigned to another student
        if bike not in checkedBikes and ans[student]==-1:
            # assign bike to student
            ans[student] = bike
            # add bike to set of checked bikes
            checkedBikes.add(bike)
    return ans

Explanation:

We first create a blank dictionary d to store the distances between each student-bike pair. We also create a blank priority queue q. We then iterate through all possible pairs of students and bikes, and calculate the distance between them using the abs() function. We insert a tuple (distance, bike index, student index) into the priority queue for each student-bike pair.

We then create an empty list ans with -1 as each element. We also create an empty set checkedBikes.

We then iterate through the priority queue, popping the bike with the shortest distance to any student. If the bike has not already been assigned to another student, and if the current student student has not yet been assigned a bike, we assign the bike to the student by setting ans[student]=bike. We also add the bike to the set of checked bikes checkedBikes.

Finally, we return the ans list.

Time Complexity:

This solution has a time complexity of O(nmlog(nm)), where n is the length of the students list and m is the length of the bikes list. We need to calculate the distances between all possible pairs of students and bikes, which takes O(nm) time. We then need to iterate through the priority queue, which takes O(nmlog(nm)) time. Therefore, the overall time complexity of this solution is O(nmlog(nm)).

Space Complexity:

This solution has a space complexity of O(nm), where n is the length of students and m is the length of bikes. We need to create a dictionary to store the distances between each student-bike pair, which takes up O(nm) space. We also need to create a priority queue to store the distances between each student-bike pair, which takes up O(nm) space. Therefore, the overall space complexity of this solution is O(nm).

1