The first round at SpaceX gave me a Beamer test problem. Briefly, it is about connecting Starlink satellites to users on the ground. Each satellite can connect to at most 32 users. If the angle between users is less than 10 degrees, the transmission band has to be switched, and one satellite has at most 4 transmission bands. A user can only see a satellite if the angle between the satellite and the direction straight above the user's head is less than 45 degrees. On top of that, you also have to account for non-Starlink high-altitude geosynchronous satellites. If a user is currently receiving data from a high-altitude non-Starlink satellite, then the angle between that high-altitude satellite, the Starlink satellite and the user has to be greater than 20 degrees. Otherwise there is interference.
Basic approach:
Step 1: start from the user's side and compute how many satellites can serve each user (the angle has to be less than 45 degrees, and the interference angle against the high-altitude satellite has to be greater than 20 degrees). Sort the users by the number of satellites that can serve them, from smallest to largest.
Step 2 (greedy): starting from the user with the fewest possible serving satellites, assign satellites step by step. Also pay attention to the angle between users: if two users on the same satellite are less than 10 degrees apart, they need to be assigned different frequency bands (prefer the band that the current satellite is using the least).
Discussion
Loading comments…