/**
 * Return the maximum population in a sunny town after
 * removing exactly one cloud.
 * https://www.hackerrank.com/challenges/cloudy-day/
 *
 * Fairly simple implementation problem.
 *
 * 1) Represent each town's location in a Skiplist.
 *  If towns share a location, simply treat them as combined.
 * 2) For each cloud, assign towns within range to it.
 * Important: remove any towns already covered by this cloud. This keeps
 * the algorithm runtime linear.
 * 3) Now for each town, group their populations by the cloud covering them.
 *
 * 4) Find the largest group, then add the uncovered towns ("NONE")
 *
 * 𝚯(M + N log N) runtime for M clouds and N towns.
 * 𝚯(M + N) space complexity 
 */
public static long maximumPeople(List<Long> p, List<Long> x, List<Long> y, List<Long> r) {
    final Cloud NONE = new Cloud(0, 0, -1L);
    // 1) Town -> Cloud
    ConcurrentSkipListMap<Long, Cloud> cover = rangeOf(x.size())
            .parallel()
            .collect(Collectors.toMap(x::get, a -> NONE, (a, b) -> a, ConcurrentSkipListMap::new));

    // 2) for each cloud, assign any virgin towns to it. Remove any others.
    rangeOf(y.size()).map(i -> new Cloud(y.get(i), r.get(i), i))
            .parallel()
            .forEach(c ->
                cover.subMap(c.start(), c.end()).forEach((a, b) -> {
                    if (b == NONE) cover.put(a, c);
                    else cover.remove(a);
                }));

    // Sum the populations for each cloud.
    Map<Long, Long> popByLocation = rangeOf(x.size()).collect(Collectors.toMap(x::get, p::get, Long::sum));
    Map<Cloud, Long> popByCloud = cover.entrySet().stream()
            .parallel()
            .collect(Collectors.groupingByConcurrent(
                Map.Entry::getValue,
                Collectors.summingLong(e -> popByLocation.get(e.getKey())))
            );

    // 3) Now find the cloud with the largest population
    long largest = popByCloud.values().stream().max(Comparator.comparingLong(e -> e)).orElse(0L);

    // 4) Sum it with uncovered towns, if any
    Long uncovered = popByCloud.remove(NONE);
    if(uncovered != null)
        largest += uncovered;
    return largest;
}
private record Cloud(long location, long range, long name) {
    long start() { return location - range; }
    long end() { return location + range + 1; } // exclusive
}
// helper function for a parallel stream
private static Stream<Integer> rangeOf(int n) {
    return IntStream.range(0, n).boxed();
}