Find maximum number of people that can go together

Question

I have been asked this question in an interview.

There are n persons, where each person have their preferences with regard to the minimum and maximum number of people they can go together with. Their preferences are represented by 2D array peoplePreferences where peoplePreferences[i][0], peoplePreferences[i][1] represent the minimum and maximum number of people person[i] can go with. We have to return the maximum people that can go together.

peoplePreferences = [[1,4], [1,2], [2,3], [1,3]]
The expected output is 3 as person[0], person[2], person[3] can go together.

I could solve this in O(n^2). I tried to optimise it by performing range operations.

• Take an extra array range of length global maximum of peoplePreference + 2(4+2=6 in example as the input would be 1 based index and 1 extra look at next step for this).
• For each person, perform this range[person[i][0]]++ and range[person[i][1] + 1]--

So, in this case it would be [0, 3, 1, -1, -2, -1]

• Use prefixSum on range-> [0, 3, 4, 3, 1, 0]

I could not proceed further. Was I going in right direction? If yes, how do I proceed?

If not, how to solve this efficiently?

Answer 1

A C++ solution. Dillon's endpoint_counter and my delta serve the same general purpose, with delta specifically tracking - as you move from delta[n] down to 1, changes in the number of participants willing to join a group of n people.

O(n) space (for delta) and time complexity.

int f(const std::vector<std::pair<int,int>>& c) {
    int n = c.size();
    std::vector<int> delta(n + 1);
    for (auto [from, to] : c)
        if (from <= n) {
            --delta[std::max(0, from - 1)];
            ++delta[std::min(n, to)];
        }
    int best = 0;
    int matched = 0;
    for (int group_size = n; group_size; --group_size) {
        matched += delta[group_size];
        best = std::max(best, std::min(matched, group_size));
        if (best >= group_size) return best;
    }
    return best;
}