Greedy Algorithms: The Array Collection problem accepts a positive integer k and
ID: 3739451 • Letter: G
Question
Greedy Algorithms:
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 1-k 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.Explanation / Answer
First of all greedy algorithms are not proper solution for some questions. Like coin change problem in dynamic problem problems. Sometimes greedy algo best choice like Dijkstra algo.
Start -
1)Create k size array and initialize every index as zero [0,0,0,0,etc].
2)As we know elements are from 1 to k then Traverse each sublist or Get first sublist or subarray from input.
3) Increment that number index into that array index
Suppose [1,2,4] array([0,0,0,0]) Then after first traverse array([1,1,0,1]).
4)If there is not already incremented array index ata that position then add that sublist into final answer.
5)traverse second array and check already incremented or no if yes then discard that whole sublist.
like wise u can traverse and use counting sort technique to address each element.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.