I am trying to design an efficient algorithm that takes as an input a list of n people and a list of pairs who know each other (as an adjacency list) and outputs the maximum number of invites given the following constraints:
- Each person should have at least p other people they know at the party
- Each person should have at least p other people they DONT know at the party
I believe I have found a solution in $O(n(n + m))$ time. Here is the pseudocode:
1.) Loop through the adjacency list counting how many attendees each attendee knows that are invited. If any attendee doesn’t meet the criteria (
num < p OR
num > current_total - p), label them as a “0” in an array representing which invitees meet the criteria. This takes $O(n + m)$ time.
2.) Repeat the above loop until it finishes with no changes being made to the invitee array. This takes $O(n)$ time.
Is there a way to beat this time complexity? If so, do I need to use a specialized data structure? Or perhaps delete nodes from the adjacency list if they dont fit the criteria as we go along?