The Array Collection problem accepts a positive integer k and collection of n sorted arrays containing integers between 1 and k. The output of this problem is a subset of the arrays such that every number 1k appears in exactly one array, or an empty set, if no solution exists. For example, if k = 5 and we are given the arrays [1, 3, 5], [1, 2, 5], [2, 3], and [2, 4], the solution would be {[1, 3, 5], [2, 4]}. Answer questions 1 and 2 below about the Array Collection problem.

1. Give pseudocode for a greedy algorithm for the Array Collection problem. Note that there is more than one reasonable answer to this problem.

2. Prove that your algorithm is not correct. (There is no greedy algorithm that correctly solves this problem.)