2. There are N animals in a shelter and there are only 2 kennels. Each kennel can hold up to N animals.
You need to find out if you can split the animals into two groups (not necessarily equal groups) such that
animals that are not compatible with each other don't go into the same kennel.
You are given an array to show incompatibility between the animals. Your function should take this array
and return True if and only if it is possible to split the group in two kennels. If you cannot split the
animals, then your function should return False.
Example: Incompatibility _array = [ [1, 3]. [1, 4], [2, 5], [2, 4] ] and N = 5 says that
1 and 3 are incompatible with each other
1 and 4 are incompatible with each other
2 and 5 are incompatible with each other
2 and 4 are incompatible with each other
Given that N = 5, your func will return True since we can split the animals such that 1,2 are in one kennel
and 3,4,5 are in another.
Greedy Algorithms (25 Pts)
Rubric:
1.
Define the problem and the data that is given
2.
Identify the objective func
3.
Give the pseudo code
4.
Base case / terminating conditions
5. Return what is needed
6. Runtime estimate