Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
279 views
in Technique[技术] by (71.8m points)

algorithm - How to cover a range using a set of ranges with minimal overlap?

Assume that there are n tasks and a group of m people which can each do a range of tasks (Ti to Tj). The cost of completing each task is k* no. of people who have completed that task. What will be minimum cost to complete all the tasks atleast once, if possible. I feel that is a Dynamic Programming problem but I am unable to reach to the optimal equation. Can someone help me reach the correct equation or the code block for above. I have attached a couple of examples for better understanding.

n:4
m:3
Range of tasks for m people: {(3,4);(1,2);(2,3)}
Answer: m1 & m2 can complete all 4 tasks so cost is 4.

Ex2:
n:4
m:2
Range of tasks for m people: {(1,3);(2,4)}
Answer: m1 & m2 are both required to complete all 4 tasks so cost is 6.
See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Answer

0 votes
by (71.8m points)

Here is the greedy algorithm - always the best place to start.

allocate all teams
IF not all sections covered
    output -1
    stop
mark all teams non-critical
flag_improved = true
WHILE( flag_improved == true )
   flag_improved = false
   find most expensive section 
   find most expensive non-critical team on most expensive section 
   IF team found that can be removed without leaving a section uncovered
       remove team
       flag_improved = true
   ELSE
       mark team critical
output cost - sum coverage of remaining teams

Here is the main function of a C++ application implementing this algorithm

main()
{
    std::vector<cTeam> teams;
    int bridge_section_count;
    Input( bridge_section_count, teams);

    // allocate all teams
    for (int s = 0; s < bridge_section_count; s++)
        Bridge.insert(std::pair(s, std::vector<cTeam>(0)));
    for (auto &t : teams)
        for (int s = t.myRange.first; s <= t.myRange.second; s++)
        {
            Bridge[s].push_back(t);
        }

    // check every section has at least one team allocated
    if (!IsCovered())
    {
        std::cout << "-1
";
        exit(1);
    }

    // loop while improvements are being found
    bool flag_improved = true;
    while (flag_improved)
    {
        flag_improved = false;

        auto most_expensive_section = find_most_expensive_section();

        while (1)
        {
            // loop over teams allocated to most expensive section
            std::vector<cTeam>::iterator most_expensive_team;
            if (!find_most_expensive_non_critical_team(
                    most_expensive_team,
                    most_expensive_section))
            {
                break;
            }

            // check can team be removed without leaving section uncovered
            if (testRemoval(*most_expensive_team))
            {
                // remove team
                doRemoval(*most_expensive_team);
                flag_improved = true;
                break;
            }
            else
            {
                // this team is critical, it cannot be removed
                most_expensive_team->myCritical = true;
            }
        }
    }
    printResult();
}

The complete application code is at https://gist.github.com/JamesBremner/ada6210a8517671abd45e882c97d526d


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...