Oscar Health

01Members Lacking Provider Network Access

You are given a list of providers and a list of members. Each provider row is encoded as [providerId, specialty, x, y]. Each member row is encoded as [memberId, x, y, requiredSpecialties], where requiredSpecialties is a pipe-delimited string such as "Cardiology|Dermatology". A member lacks adequate provider network access if there exists at least one required specialty for which no provider of that specialty lies within maxDistance of the member. Use Euclidean distance. Return the ids of all members who lack adequate access in ascending order. Function Description Complete the function findMembersLackingAccess in the editor below. findMembersLackingAccess has the following parameters:

String[][] providers: provider rows [providerId, specialty, x, y]
String[][] members: member rows [memberId, x, y, requiredSpecialties]
int maxDistance: the maximum allowed Euclidean distance Returns int[]: the ids of members lacking adequate access, sorted ascending.

Constraints

1 ≤ providers.length, members.length ≤ 10⁵
Coordinates are numeric values stored as strings in the encoded input.
A member is reported if any required specialty is missing within maxDistance.
The answer must be sorted ascending for deterministic output.

Example 1

Input:

providers = [["1", "Cardiology", "1", "2"], ["2", "Dermatology", "3", "4"]]
members = [["101", "2", "3", "Cardiology|Dermatology"], ["102", "10", "10", "Cardiology"]]
maxDistance = 5

Output:

[102]

Explanation: Member 101 has both required specialties within distance 5. Member 102 has no nearby cardiology provider.

Example 2

Input:

providers = [["1", "Cardiology", "0", "0"]]
members = [["1", "3", "4", "Cardiology"], ["2", "0", "0", "Dermatology"]]
maxDistance = 5

Output:

[2]

Explanation: Member 1 is exactly distance 5 from the cardiology provider, so access is adequate. Member 2 requires dermatology, which is unavailable.

解法

按 specialty 分组所有 providers 的坐标。对每个 member，遍历其 requiredSpecialties，对每个 specialty 检查是否存在距离 ≤ maxDistance 的 provider；只要有一个 specialty 找不到，该 member 就纳入结果。简单实现 O(M·R·P)。若量级大可对每 specialty 建 KD-Tree 加速到 O(M·R·log P)，下方给出朴素扫描以保证可读性。比较距离时用平方避免开方。返回 id 升序。

from collections import defaultdict
from typing import List

def find_members_lacking_access(providers: List[List[str]], members: List[List[str]], max_distance: int) -> List[int]:
    by_spec = defaultdict(list)
    for pid, spec, x, y in providers:
        by_spec[spec].append((float(x), float(y)))
    md2 = max_distance * max_distance
    bad = []
    for mid, mx, my, specs in members:
        mxf, myf = float(mx), float(my)
        lack = False
        for s in specs.split("|"):
            pts = by_spec.get(s, [])
            if not any((px - mxf) ** 2 + (py - myf) ** 2 <= md2 for px, py in pts):
                lack = True
                break
        if lack:
            bad.append(int(mid))
    bad.sort()
    return bad

import java.util.*;

class Solution {
    public int[] findMembersLackingAccess(String[][] providers, String[][] members, int maxDistance) {
        Map<String, List<double[]>> bySpec = new HashMap<>();
        for (String[] p : providers) {
            bySpec.computeIfAbsent(p[1], k -> new ArrayList<>()).add(new double[]{Double.parseDouble(p[2]), Double.parseDouble(p[3])});
        }
        double md2 = (double) maxDistance * maxDistance;
        List<Integer> bad = new ArrayList<>();
        for (String[] m : members) {
            double mx = Double.parseDouble(m[1]), my = Double.parseDouble(m[2]);
            boolean lack = false;
            for (String s : m[3].split("\\|")) {
                List<double[]> pts = bySpec.getOrDefault(s, Collections.emptyList());
                boolean found = false;
                for (double[] pt : pts) {
                    double dx = pt[0] - mx, dy = pt[1] - my;
                    if (dx * dx + dy * dy <= md2) { found = true; break; }
                }
                if (!found) { lack = true; break; }
            }
            if (lack) bad.add(Integer.parseInt(m[0]));
        }
        Collections.sort(bad);
        return bad.stream().mapToInt(Integer::intValue).toArray();
    }
}

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<int> findMembersLackingAccess(vector<vector<string>>& providers, vector<vector<string>>& members, int maxDistance) {
        unordered_map<string, vector<pair<double,double>>> bySpec;
        for (auto& p : providers) bySpec[p[1]].push_back({stod(p[2]), stod(p[3])});
        double md2 = (double)maxDistance * maxDistance;
        vector<int> bad;
        for (auto& m : members) {
            double mx = stod(m[1]), my = stod(m[2]);
            bool lack = false;
            stringstream ss(m[3]); string spec;
            while (getline(ss, spec, '|')) {
                bool found = false;
                for (auto& [px, py] : bySpec[spec]) {
                    double dx = px - mx, dy = py - my;
                    if (dx * dx + dy * dy <= md2) { found = true; break; }
                }
                if (!found) { lack = true; break; }
            }
            if (lack) bad.push_back(stoi(m[0]));
        }
        sort(bad.begin(), bad.end());
        return bad;
    }
};