CODEWITHSUNDEEP
c++algorithm
Andrew
Andrew

Reputation: 13

How to optimize matches to ranges (homework)

I'm taking a first-year programming course and this is an assignment question, so I'd appreciate a few pointers but not the answer.

The question was, given a list of some number of ordered elements, how do you slot them into given ordered ranges such that the maximum number of elements are slotted? (The number of ranges and elements not necessarily being equal)

This example input was given:

Elements: 2, 6, 7, 8, 9
Ranges: 0-3, 2-5, 3-9, 8-10

The output for this would be 3, as 2 would slot into 2-5 (or 0-3), 6/7 would slot into 4-9, and 9 would slot into 8-13.

What I've tried so far is to try a greedy approach. That seems to fail as there are many cases where it doesn't work, for example:

Elements: 2, 5
Ranges: 0-7, 2-3

Processing the elements first slots 2 into 0-7, but then 5 has nowhere to go (and it's clear upon inspection that the max is 2). I'm not quite sure how to proceed - a hint or two would be much appreciated!

Upvotes: 1

Views: 55

Answers (1)

algojava
algojava

Reputation: 753

You can use maximum bipartite matching to solved this problem.

Edit: Or you can sorting the Ranges in ascending order by second value.

Examples: Ranges: 0-7, 2-3 will be 2-3, 0-7

Then you can use your greedy approach.

Upvotes: 1

Related Questions