You are given a range [first, last], initially white. You need to paint it black.

For this purpose you have a set of triples

[(f, l, cost), …] – where each triple means that you can paint the range [f, l] for ‘cost’ coins (limitations: cost is floating point >= 0; f, l are integers representing start and end of the range to be painted black).

Find minimum cost needed to paint the whole range [first, last] or return -1 if it’s impossible

Example:

[first, last] = [0, 5] and set of triples are

[[0, 5, 10], [0, 4, 1], [0, 2, 5], [2, 5, 1]]

Clearly the answer is to take [0, 4, 1] and [2, 5, 1] – the total cost will be 2.

Another example:

[first, last] = [0, 5]

triples are [[1,4, 10], [2, 5, 6]]

answer is -1, because it’s impossible to color the whole range.

```
using System;
using System.Collections.Generic;
using System.Collections;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
namespace ConsoleApplication1
{
public class Triplet
{
public int start;
public int end;
public float cost;
}
class Program
{
public static void Main(string[] args)
{
string rangeStr = "[0, 5]";
string tripletStr = "[0, 5, 10], [0, 4, 1], [0, 2, 5], [2, 5, 1]";
char[] trimChar = { '[', ']' };
Regex reg = new Regex(",");
string[] rangeSplit = reg.Split(rangeStr.Trim(trimChar));
int start = int.Parse(rangeSplit[0].Trim());
int end = int.Parse(rangeSplit[1].Trim());
Triplet[] triplets = ParseTriplet(tripletStr);
//Filter out valid triplets
ArrayList al = new ArrayList();
for (int i = 0; i < triplets.Length; i++)
{
if ((start >= triplets[i].start && start < triplets[i].end) || (end > triplets[i].start && end <= triplets[i].end) || (triplets[i].start >= start && triplets[i].start < end) || (triplets[i].end > start && triplets[i].end <= end))
{
al.Add(i);
}
}
//Generate combinations
float minCost = 0; ArrayList comboList = new ArrayList();
int flag = 0;
int maxLimit = (int)Math.Pow(2, al.Count) - 1;
for (int i = 1; i <= maxLimit; i++)
{
string binary = DecimalToBinary(i).PadLeft(al.Count, '0');
float tempCost = 0; ArrayList tempList = new ArrayList();
for (int j = 0; j < binary.Length; j++)
{
if (binary[j] != '0')
{
tempCost = tempCost + triplets[(int)al[j]].cost;
tempList.Add(triplets[(int)al[j]]);
}
}
//Check for valid combinations
if (ValidCombo(tempList, start, end))
{
if (flag == 0)
{
flag = 1;
comboList.AddRange(tempList);
minCost = tempCost;
}
else if (tempCost < minCost)
{
comboList.Clear();
comboList.AddRange(tempList);
minCost = tempCost;
}
}
}
if (comboList.Count == 0)
{
Console.WriteLine("No solution found...");
}
else
{
Console.WriteLine("Minimum Cost = " + minCost);
for (int i = 0; i < comboList.Count; i++)
{
Console.WriteLine("[" + ((Triplet)comboList[i]).start + ", " + ((Triplet)comboList[i]).end + ", " + ((Triplet)comboList[i]).cost + "]");
}
}
}
public static bool ValidCombo(ArrayList tempList, int start, int end)
{
Hashtable ht = CreateHashTable(start, end);
for (int i = 0; i < tempList.Count; i++)
{
for (int j = ((Triplet)tempList[i]).start; j < ((Triplet)tempList[i]).end; j++)
{
if (ht.Contains(j.ToString() + ";" + (j + 1).ToString()))
{
ht[j.ToString() + ";" + (j + 1).ToString()] = 1;
}
}
}
return CheckHashTable(ht);
}
public static bool CheckHashTable(Hashtable ht)
{
foreach (DictionaryEntry entry in ht)
{
if ((int)entry.Value == 0)
return false;
}
return true;
}
public static Hashtable CreateHashTable(int start, int end)
{
Hashtable ht = new Hashtable();
for (int i = start; i < end; i++)
{
ht.Add(i.ToString() + ";" + (i + 1).ToString(), 0);
}
return ht;
}
public static string DecimalToBinary(int num)
{
string rem = "";
while (num >= 1)
{
int quot = num / 2;
rem += (num % 2).ToString();
num = quot;
}
// Reversing the value
string bin = "";
for (int i = rem.Length - 1; i >= 0; i--)
{
bin = bin + rem[i];
}
return bin;
}
public static Triplet[] ParseTriplet(string tripletStr)
{
Triplet[] triplets = new Triplet[GetNumberOfTriplets(tripletStr)];
string tempStr = ""; int flag = 0, counter = 0;
for (int i = 0; i < tripletStr.Length; i++)
{
if (tripletStr[i] == '[')
{
flag = 1;
}
else if (tripletStr[i] == ']')
{
flag = 0;
Regex reg = new Regex(",");
string[] tripletSplit = reg.Split(tempStr);
triplets[counter] = new Triplet();
triplets[counter].start = int.Parse(tripletSplit[0].Trim());
triplets[counter].end = int.Parse(tripletSplit[1].Trim());
triplets[counter].cost = float.Parse(tripletSplit[2].Trim());
counter++;
tempStr = "";
}
else if (flag == 1)
{
tempStr = tempStr + tripletStr[i];
}
}
return triplets;
}
public static int GetNumberOfTriplets(string tripletStr)
{
int count = 0;
for (int i = 0; i < tripletStr.Length; i++)
{
if (tripletStr[i] == '[')
count++;
}
return count;
}
}
}
```

Output
=======
Minimum Cost = 2
[0, 4, 1]
[2, 5, 1]
Press any key to continue . . .