Tuesday, October 28, 2014

UVa Problem 10020 - Minimal coverage

Problem:

Please find the problem here.

Solution:

This is the first problem that involves a greedy algorithm I solved on UVa. The basic idea is to pick the interval so that it covers as much as possible to the right without creating holes.

So suppose I have these intervals:

[0, 4]
[1, 2]
[2, 5]
[3, 7]
[5, 7]

First thing first, we must cover 0, so we have no choice but picking [0, 4] as our first interval.

Next, we look at [1, 2], there is no point picking [1, 2] at all, we cannot cover anything more with this.

Then, we consider [2, 5], well, we might be able to cover more space with [2, 5], so let's consider it.

Then, we consider [3, 7], now we know [2, 5] is useless because we can cover more space with [3, 7] than [2, 5], note that [3, 7] does not cover [2, 3), but that does not matter, for we have already covered [2, 3) using our first [0. 4], now we are considering [3, 7]

Next, we consider [5, 7], note that [5, 7] does not cover (4, 5), so we decide [3, 7] is what we will pick, as it cover most space subjected to the no hole constraint.

To prove that the greedy algorithm works, we use the greedy algorithm stay ahead techniques. The algorithm maximize the space given least number of segments, so it minimize the number segment given the space constraint!

Code:


#include "stdafx.h"

// http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=961

#include "UVa10020.h"

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

int UVa10020()
{
    int number_of_test_cases;
    cin >> number_of_test_cases;
    for (int c = 0; c < number_of_test_cases; c++)
    {
        int m;
        cin >> m;
        vector<pair<int, int> > intervals;
        while (true)
        {
            int from;
            int to;
            cin >> from;
            cin >> to;
            if (from == 0 && to == 0)
            {
                break;
            }
            intervals.push_back(pair<int, int>(from, to));
        }

        // Start greedy algorithm
        int uncovered_index = 0;

        sort(intervals.begin(), intervals.end());

        // Constructing max cover
        vector<pair<int, int> > max_cover;
        int required_min = 0;
        bool current_best_valid = false;
        pair<int, int> current_best;
        bool feasible = true;
        for (vector<pair<int, int> >::iterator ii = intervals.begin(); ii != intervals.end(); ii++)
        {
            pair<int, int> current = *ii;
            if (current.first <= required_min)
            {
                if (current.second > current_best.second)
                {
                    current_best.first = current.first;
                    current_best.second = current.second;
                    current_best_valid = true;
                }
            }
            else
            {
                if (current_best_valid)
                {
                    // Current best is the actual best - nothing beyond this will meet the requirement
                    max_cover.push_back(current_best);

                    // Now we require more!
                    required_min = current_best.second;
                    current_best_valid = false;

                    if (required_min >= m)
                    {
                        // I have already covered M, we can stop now
                        break;
                    }
                }

                if (current.first <= required_min)
                {
                    if (current.second > current_best.second)
                    {
                        current_best.first = current.first;
                        current_best.second = current.second;
                        current_best_valid = true;
                    }
                }
                else
                {
                    feasible = false;
                    break;
                }
            }
        }
        if (current_best_valid)
        {
            max_cover.push_back(current_best);
        }

        if (feasible)
        {
            cout << max_cover.size() << endl;
            for (vector<pair<int, int> >::iterator ii = max_cover.begin(); ii != max_cover.end(); ii++)
            {
                cout << ii->first << " " << ii->second << endl;
            }
        }
        else
        {
            cout << 0 << endl;
        }

        if (c != number_of_test_cases - 1)
        {
            cout << endl;
        }
    }
    return 0;
}

2 comments :

  1. i didnt get the question .. can u please elaborate

    ReplyDelete
  2. The question?
    The problem can be found in this link:
    http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=961

    ReplyDelete