Is It Possible to Satisfy Everyone?
You are given two sets of nodes, each with the same number of nodes. Set A contains a list of people. Set B contains a list of items. Each person has a preference for any number of items in Set B. If we represent these preferences as connections between the person nodes and item nodes, each node must have at least one connection.
Initially I thought that each person can always get their desired item, but this is not always true, for example something like this may happen:
One thought I had was that as long as there are (set A size + set B size-1) or more connections in the graph, it's always possible to form valid connections. However, I'm having troubles proving the correctness of this. Do you know if this is correct? Or is there a different solution completely?
I would approach this problem the following way:
Sort people of A by the number of edges they have (from lower to higher).
If a person in A has only one prefered item in B, assign it.
When a person in A has more than one prefered item in B, choose the item with the smallest number of people in A that prefer it.
I'd do this with backtracking.
- What is the complexity of the sorted() function?
- Implementation for a Monotonic Increasing Queue
- Java, Shifting Elements in an Array
- Differences between backtracking and brute-force search
- Number of partition of `n` into sum of three squares (fast algorithm)
- Big Number Subtraction in C
- If the n-body problem is chaotic, why isn't it used as a RNG?
- Using BFS for Weighted Graphs
- Removing a node in an undirected graph that destroys a path between two other nodes
- Binary search function is correct but it returns undefined
- Algorithm to reverse an array/string only in terms of rotate operations
- Correctness of Deletion algorithm of BST in CLRS
- Time Complexities n(log(n)) and log(n^n)
- How do I find the closest possible sum of an array's elements to a particular value?
- Split on regex (more than a character, maybe variable width) and keep the separator like GNU awk
- Find the minimum number of edits to balance parentheses?
- How to improve pandas DF processing time on different combinations of calculated data
- Efficiently calculate an availability date from a list of project assignments and known capacity
- Optimized algorithm to schedule tasks with dependency?
- Difference between back tracking and dynamic programming
- Javascript data structures library
- Segmentation error when implementing the Hoare quick sort method
- Which of these implementations is canonical: storing the head and size variables, or storing the head, tail, and size?
- Visualization of calendar events. Algorithm to layout events with maximum width
- Tracing edges of pixels in a mask
- Longest Subarray with Maximum Bitwise AND
- Assigning codes to nodes such that codes are unique and create two groups which share common properties
- Randomly Split a Graph into Mini Graphs
- Recursion relation and overlapping sub problems
- Calculating the 90th percentile in O(n) time