Practice/Meta/Optimize Meeting Point for Friends in a Graph

Optimize Meeting Point for Friends in a Graph

CodingMust

Problem

You are organizing a meetup for a group of friends who are currently at different locations within a city network. The city is represented as an undirected graph where nodes represent locations and edges represent direct paths between locations. Each edge has equal weight, meaning traveling along any edge takes exactly one unit of time.

Given the positions of all friends and a list of potential meeting venues, determine which venue minimizes the total travel time for all friends combined. Return the node number of the optimal meeting location. If multiple venues have the same minimal total travel time, return the one with the smallest node number.

Requirements

1. Calculate the shortest path distance from each friend's location to each potential meeting point
2. For each meeting point, compute the sum of all friends' travel distances to that point
3. Return the meeting point with the minimum total distance
4. If there's a tie, return the meeting point with the smaller node number
5. Handle cases where some friends cannot reach certain meeting points (treat as invalid/infinite distance)

Constraints

• 2 <= n <= 1000 (number of nodes in the graph)
• 1 <= edges.length <= min(n * (n-1) / 2, 5000) (number of edges)
• 1 <= friends.length <= 100 (number of friends)
• 1 <= meetingPoints.length <= 100 (number of potential venues)
• 0 <= friends[i], meetingPoints[i] < n
• The graph may be disconnected
• Multiple friends can be at the same location
• All edges are bidirectional with unit weight

Examples

Example 1:

` Input: n = 4 edges = [[0,1],[1,2],[2,3]] friends = [0,3] meetingPoints = [1,2]

Output: 1

Explanation:

• Meeting at node 1: friend at 0 travels 1 unit, friend at 3 travels 2 units → total = 3
• Meeting at node 2: friend at 0 travels 2 units, friend at 3 travels 1 unit → total = 3
• Both are equal, so return the smaller node number: 1 `

Example 2:

` Input: n = 5 edges = [[0,1],[1,2],[2,3],[3,4]] friends = [0,2,4] meetingPoints = [1,2,3]

Output: 2

Explanation:

• Meeting at node 1: distances are [1,1,3] → total = 5
• Meeting at node 2: distances are [2,0,2] → total = 4 (minimum)
• Meeting at node 3: distances are [3,1,1] → total = 5
• Node 2 has the minimum total distance `

Example 3:

` Input: n = 3 edges = [[0,1]] friends = [0,2] meetingPoints = [1]

Output: 1

Explanation:

• Friend at node 2 cannot reach node 1 (disconnected)
• This makes the meeting point invalid in strict interpretation
• However, if we must return a meeting point, return the only available one `