## Tuesday, October 28, 2014

### UVa Problem 10020 - Minimal coverage

Problem:

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;
}