Array Partitioning

Question

I have a set of object numbered from 1 to n and there is only one instance of each object.Now say, I have received k request, each request is to get some set of object. So how I should process these requests so that we can process maximum number of request. we have prior knowledge of all the request.

---

Ex: say we have 10 apple numbered from 1 to 10 and three requests:

request 1: {2,6}

request 2: {1,2,3,4,5}

request 3: {6,7,8,9,10}

so here if we process request 1 then we can full-fill only 1 request but if we process 2 and 3 we can full-fill 2 request. Please suggest a optimized Algo.

Answer 1

The problem you describe is called maximum set packing: given a set (your array) an a set of subsets (your requests), find the maximum number of subsets (requests) that do not have an element in common (are pairwise disjoint).

As shown in the wikipedia article, the problem can be formulated as an integer linear program, which can be solved by a standard solver. Since those are highly optimized, that is as optimal as you can probably get. Like many packing problems, the problem is NP-hard, so you cannot do much better than brute-force if you try to implement this yourself.