Google Interview Question Software Developers
Country: United States
Interview Type: In-Person
class Range implements Comparable<Range>{
private int l;
private int r;
private double cost;
public Range(int i, int j, int k) {
l = i;
r = j;
cost = k;
}
@Override
public int compareTo(Range obj) {
if (r == obj.r) {
return obj.l - l;
}
return r - obj.r;
}
}
double minCost(Range[] ranges, int L, int R) {
double[] dp = new double[R + 1];
for (int j = L + 1; j <= R; j++) {
double min = Double.MAX_VALUE;
int i = ranges.length - 1;
while (i >= 0) {
if (ranges[i].r >= j&& ranges[i].l < j) {
if (dp[ranges[i].l] != -1 && dp[ranges[i].l] + ranges[i].cost < min) {
min = dp[ranges[i].l] + ranges[i].cost;
}
}
i--;
}
if (min == Double.MAX_VALUE) {
dp[j] = -1;
}
else
dp[j] = min;
}
return dp[R];
}
//Assumptions each of the range objects somehow overlaps with first and last.
public class Range{
int left;
int right;
cost;
}
public int minCost(int start,int end, Range[] arr)
{
if(start<end||start<0||end<0||arrr==null||arr.length==0)
{
return -1}
double[][] m=new double[end-start+1][end-start+1];
for(int r=0;r<m.length;r++)
{
for(int c=0;c<m[0].length;c++)
{
m[r][c]=-1.0;
}
}
for(int i=0;i<arr.length;i++)
{
Range entry=arr[i];
int row=start-start;
int col=end-start;
if(entry.left>=start && entry.left<=end)
{
row=entry.left-start;
}
if(entry.right>=start && entry.right<=end)
{
col=entry.right-start;
}
m[row][col]=m[row][col]==-1.0||m[row][col]>entry.cost?entry.cost:m[row][cost];
}
for(int c=m[0].length-1;c>=0;c--)
{
if(m[0][c]==-1.0 ||m[0][c]>m[0][c+1] && m[0][c+1]>0.00))
{
m[0][c]=m[0][c+1];
}
}
for(int r=1;r<m.length;r++)
{
int col=m[0].length-1;
m[r][col]=m[r][col]==(-1.0||(m[r][col]>m[r-1][col] && m[r-1][col]>0.0))?m[r-1][col]:m[r][col];
while(col>=r)
{
m[r][col]=m[r][col]==-1.0||(m[r][col]>m[r][col+1] && m[r][col+1]>0.0)?m[r][col+1]:m[r][col];
m[r][col]=m[r][col]==(-1.0||(m[r][col]>m[r-1][col] && m[r-1][col]>(float)0.0)?m[r-1][col]:m[r][col];
col--;
}
}
double minCost=-1.0;
for(int i=0;i<arr.length;i++)
{
double total=arr[i].cost;
if((end-entry.right)>0 && (m[entry.right+1][last]>0.0))
{
total+= m[entry.right][last];
}
if((entry.left-start)>0 && (m[start][entry.left-1]>0.0))
{
total+=m[start][entry.left-1];
}
minCost=minCost==-1.0||total<minCost?total:minCost;
}
return minCost;
}
/**Time Complexity: O(NM + M^2) where N is the number of range objects and M is the size of the range between first and last.
Space Complexity: O(M^2)**/
C++, implementation, O(2^n * n^2)
struct Paint {
int f;
int l;
float cost;
};
bool coverAllRange(int first, int last, vector<Paint>& arr, vector<int>& v) {
vector<pair<int, int>> ranges, temp;
int f, l, i, j;
bool overlap;
for (i = 0; i < v.size(); i++) {
if (v[i] == 0) continue;
overlap = false;
f = arr[i].f;
l = arr[i].l;
for (j = 0; j < ranges.size(); j++) {
if (arr[i].f <= ranges[j].second && arr[i].l >= ranges[j].first) {
if (overlap == false) {
overlap = true;
f = min(arr[i].f, ranges[j].first);
l = max(arr[i].l, ranges[j].second);
} else {
f = min(f, min(arr[i].f, ranges[j].first));
l = max(l, max(arr[i].l, ranges[j].second));
}
if (f <= first && l >= last) return true;
} else {
temp.push_back(ranges[j]);
}
}
ranges = temp;
ranges.push_back(make_pair(f, l));
temp.clear();
}
return false;
}
float solve(int first, int last, vector<Paint>& arr) {
queue<pair<int, vector<int>>> q;
vector<int> v;
int i, r;
float cost, temp;
cost = -1.0;
q.push(make_pair(arr.size(), v));
while (!q.empty()) {
r = q.front().first;
v = q.front().second;
q.pop();
if (r > 0) {
v.push_back(0);
q.push(make_pair(r - 1, v));
v[v.size() - 1] = 1;
q.push(make_pair(r - 1, v));
} else {
if (coverAllRange(first, last, arr, v) == true) {
temp = 0.0;
for (i = 0; i < v.size(); i++) {
if (v[i] == 1) temp += arr[i].cost;
}
if (cost == -1.0 || cost > temp) cost = temp;
}
}
}
return cost;
}
Python Solution:
def paint_range(range_, tokens):
def _is_overlap(r, t):
return not (r[0] > t[1] and r[1] < t[0])
def _split_range(ranges, t):
# Given a token, returns the ramaining parts to paint
result = []
for r in ranges:
if _is_overlap(r, t):
tmp = [(r[0], t[0] - 1), (t[1] + 1, r[1])]
result.extend(x for x in tmp if x[1] - x[0] >= 0)
else:
result.append(r)
return result
def _is_useful(ranges, t):
# Check if we should use a given token
for r in ranges:
if _is_overlap(r, t):
return True
return False
def _paint_range(ranges, tokens, cost):
# print "New Call: %s %s %s" % (str(ranges), str(tokens), str(cost))
if not ranges:
# Found a value
return cost
if not tokens:
# There are ranges left, return inf
return float('inf')
min_cost = float('inf')
for i, t in enumerate(tokens):
if _is_useful(ranges, t):
min_cost = min(min_cost, _paint_range(_split_range(ranges, t),
tokens[:i] + tokens[i + 1:],
cost + t[2]))
return min_cost
return _paint_range([tuple(range_)], tokens, 0)
print paint_range([0, 5], [(0, 5, 10), (0, 4, 1), (0, 2, 5), (2, 5, 1)])
print paint_range([0, 5], [(1, 4, 10), (2, 5, 6)])
print paint_range([2, 6], [])
print paint_range([2, 6], [(3, 3, 1), (0, 8, 12), (2, 2, 1), (4, 6, 1)])
public class PaintRange
{
public int first;
public int last;
public int cost;
public PaintRange(int first, int last, int cost)
{
this.first = first;
this.last = last;
this.cost = cost;
}
}
public class PaintRangeBlack
{
public int FindMinimumCost(int first, int last, int cost, List<PaintRange> ranges)
{
int minCost = Int32.MaxValue;
int oldcost = cost;
foreach (var range in ranges)
{
if (range.first <= first && range.last > first)
{
if (minCost == Int32.MaxValue || cost + range.cost < minCost)
{
cost += range.cost;
if (range.last < last)
{
int temp = FindMinimumCost(range.last, last, cost, ranges);
if (temp != Int32.MaxValue && minCost>temp)
minCost = temp;
}
if (range.last >= last && minCost > cost)
{
minCost = cost;
cost = oldcost;
}
}
}
cost = oldcost;
}
return minCost;
}
}
def findCost(start, end, costs):
minsofar = -1
for idx, cost in enumerate(costs):
if cost[1] < start or cost[0] > start:
continue
currcost = None
if cost[1] >= end:
currcost = cost[2]
else:
if idx+1 < len(costs):
currcost = findCost(cost[1], end, costs[:idx] + costs[idx+1:])
if currcost is not None:
currcost += cost[2]
if minsofar == -1 or (currcost and minsofar > currcost):
minsofar = currcost
return minsofar
print(findCost(0, 5, [[0, 5, 10], [0, 4, 1], [0, 2,5], [2, 5, 1]]))
print(findCost(5, 10, [[0, 5, 10], [0, 4, 1], [0, 2,5], [2, 5, 1], [1, 11, 4]]))
print(findCost(0, 10, [[1, 5, 1], [0, 6, 2], [2, 8, 3], [5, 10, 1], [0, 11, 8]]))
print(findCost(0, 5, [[0, 5, 10], [0, 3, 1], [3, 4, 2], [3, 4, 1], [4, 5, 1], [0, 2, 5]]))
print(findCost(0, 5, [[1,4, 10], [2, 5, 6]]))
output:
2
4
3
3
-1
def findCost(start, end, costs):
minsofar = -1
for idx, cost in enumerate(costs):
if cost[1] < start or cost[0] > start:
continue
currcost = None
if cost[1] >= end:
currcost = cost[2]
else:
if idx+1 < len(costs):
currcost = findCost(cost[1], end, costs[:idx] + costs[idx+1:])
if currcost is not None:
currcost += cost[2]
if minsofar == -1 or (currcost and minsofar > currcost):
minsofar = currcost
return minsofar
print(findCost(0, 5, [[0, 5, 10], [0, 4, 1], [0, 2,5], [2, 5, 1]]))
print(findCost(5, 10, [[0, 5, 10], [0, 4, 1], [0, 2,5], [2, 5, 1], [1, 11, 4]]))
print(findCost(0, 10, [[1, 5, 1], [0, 6, 2], [2, 8, 3], [5, 10, 1], [0, 11, 8]]))
print(findCost(0, 5, [[0, 5, 10], [0, 3, 1], [3, 4, 2], [3, 4, 1], [4, 5, 1], [0, 2, 5]]))
print(findCost(0, 5, [[1,4, 10], [2, 5, 6]]))
output:
2
4
3
3
-1
public static Function()
{
int F = 0;
int L = 5;
float C = -1;
Dictionary<int, bool> w = new Dictionary<int, bool>();
for (int i = F; i <= L; i++)
{
w.Add(i, false);
}
string tupleList = "[0, 5, 10], [0, 4, 7], [0, 2, 5], [2, 5, 1]";//"[1,4, 10], [2, 5, 6]";
List<Tuple> tuples = new List<Tuple>();
foreach (string tuple in tupleList.Split(']'))
{
if (tuple.Length < 5)
{
continue;
}
string temp = tuple.Trim(new char[] { ',', ']', '[', ' '});
string[] fields = temp.Split(',');
Tuple tempTuple = new Tuple
{
f = int.Parse(fields[0]),
l = int.Parse(fields[1]),
c = float.Parse(fields[2])
};
tuples.Add(tempTuple);
}
Dictionary<HashSet<int>, float> solutions = new Dictionary<HashSet<int>, float>();
for (int i = 0; i < tuples.Count; i++)
{
int f = F;
int l = L;
float c = 0;
HashSet<int> chosen = new HashSet<int>();
for (int j = i; j < tuples.Count; j++)
{
Tuple current = tuples[j];
bool anyUsed = false;
for (int k = current.f; k <= current.l; k++)
{
if (!w[k])
{
anyUsed = true;
w[k] = true;
}
}
if (anyUsed)
{
c += current.c;
chosen.Add(j);
}
bool allPainted = w.Values.All(r => r == true);
if (allPainted)
{
solutions.Add(chosen, c);
for (int m = F; m <= L; m++)
{
w[m] = false;
}
break;
}
}
}
}
struct Tuple
{
public int f;
public int l;
public float c;
}
public static void Function7()
{
int F = 0;
int L = 5;
float C = -1;
Dictionary<int, bool> w = new Dictionary<int, bool>();
for (int i = F; i <= L; i++)
{
w.Add(i, false);
}
string tupleList = "[0, 5, 10], [0, 4, 7], [0, 2, 5], [2, 5, 1]";//"[1,4, 10], [2, 5, 6]";
List<Tuple> tuples = new List<Tuple>();
foreach (string tuple in tupleList.Split(']'))
{
if (tuple.Length < 5)
{
continue;
}
string temp = tuple.Trim(new char[] { ',', ']', '[', ' '});
string[] fields = temp.Split(',');
Tuple tempTuple = new Tuple
{
f = int.Parse(fields[0]),
l = int.Parse(fields[1]),
c = float.Parse(fields[2])
};
tuples.Add(tempTuple);
}
Dictionary<HashSet<int>, float> solutions = new Dictionary<HashSet<int>, float>();
for (int i = 0; i < tuples.Count; i++)
{
int f = F;
int l = L;
float c = 0;
HashSet<int> chosen = new HashSet<int>();
for (int j = i; j < tuples.Count; j++)
{
Tuple current = tuples[j];
bool anyUsed = false;
for (int k = current.f; k <= current.l; k++)
{
if (!w[k])
{
anyUsed = true;
w[k] = true;
}
}
if (anyUsed)
{
c += current.c;
chosen.Add(j);
}
bool allPainted = w.Values.All(r => r == true);
if (allPainted)
{
solutions.Add(chosen, c);
for (int m = F; m <= L; m++)
{
w[m] = false;
}
break;
}
}
}
}
struct Tuple
{
public int f;
public int l;
public float c;
}
public static void Function7()
{
int F = 0;
int L = 5;
float C = -1;
Dictionary<int, bool> w = new Dictionary<int, bool>();
for (int i = F; i <= L; i++)
{
w.Add(i, false);
}
string tupleList = "[0, 5, 10], [0, 4, 7], [0, 2, 5], [2, 5, 1]";//"[1,4, 10], [2, 5, 6]";
List<Tuple> tuples = new List<Tuple>();
foreach (string tuple in tupleList.Split(']'))
{
if (tuple.Length < 5)
{
continue;
}
string temp = tuple.Trim(new char[] { ',', ']', '[', ' '});
string[] fields = temp.Split(',');
Tuple tempTuple = new Tuple
{
f = int.Parse(fields[0]),
l = int.Parse(fields[1]),
c = float.Parse(fields[2])
};
tuples.Add(tempTuple);
}
Dictionary<HashSet<int>, float> solutions = new Dictionary<HashSet<int>, float>();
for (int i = 0; i < tuples.Count; i++)
{
int f = F;
int l = L;
float c = 0;
HashSet<int> chosen = new HashSet<int>();
for (int j = i; j < tuples.Count; j++)
{
Tuple current = tuples[j];
bool anyUsed = false;
for (int k = current.f; k <= current.l; k++)
{
if (!w[k])
{
anyUsed = true;
w[k] = true;
}
}
if (anyUsed)
{
c += current.c;
chosen.Add(j);
}
bool allPainted = w.Values.All(r => r == true);
if (allPainted)
{
solutions.Add(chosen, c);
for (int m = F; m <= L; m++)
{
w[m] = false;
}
break;
}
}
}
}
struct Tuple
{
public int f;
public int l;
public float c;
}
public static void Function7()
{
int F = 0;
int L = 5;
float C = -1;
Dictionary<int, bool> w = new Dictionary<int, bool>();
for (int i = F; i <= L; i++)
{
w.Add(i, false);
}
string tupleList = "[0, 5, 10], [0, 4, 7], [0, 2, 5], [2, 5, 1]";//"[1,4, 10], [2, 5, 6]";
List<Tuple> tuples = new List<Tuple>();
foreach (string tuple in tupleList.Split(']'))
{
if (tuple.Length < 5)
{
continue;
}
string temp = tuple.Trim(new char[] { ',', ']', '[', ' '});
string[] fields = temp.Split(',');
Tuple tempTuple = new Tuple
{
f = int.Parse(fields[0]),
l = int.Parse(fields[1]),
c = float.Parse(fields[2])
};
tuples.Add(tempTuple);
}
Dictionary<HashSet<int>, float> solutions = new Dictionary<HashSet<int>, float>();
for (int i = 0; i < tuples.Count; i++)
{
int f = F;
int l = L;
float c = 0;
HashSet<int> chosen = new HashSet<int>();
for (int j = i; j < tuples.Count; j++)
{
Tuple current = tuples[j];
bool anyUsed = false;
for (int k = current.f; k <= current.l; k++)
{
if (!w[k])
{
anyUsed = true;
w[k] = true;
}
}
if (anyUsed)
{
c += current.c;
chosen.Add(j);
}
bool allPainted = w.Values.All(r => r == true);
if (allPainted)
{
solutions.Add(chosen, c);
for (int m = F; m <= L; m++)
{
w[m] = false;
}
break;
}
}
}
}
struct Tuple
{
public int f;
public int l;
public float c;
}
public static void Function7()
{
int F = 0;
int L = 5;
float C = -1;
Dictionary<int, bool> w = new Dictionary<int, bool>();
for (int i = F; i <= L; i++)
{
w.Add(i, false);
}
string tupleList = "[0, 5, 10], [0, 4, 7], [0, 2, 5], [2, 5, 1]";//"[1,4, 10], [2, 5, 6]";
List<Tuple> tuples = new List<Tuple>();
foreach (string tuple in tupleList.Split(']'))
{
if (tuple.Length < 5)
{
continue;
}
string temp = tuple.Trim(new char[] { ',', ']', '[', ' '});
string[] fields = temp.Split(',');
Tuple tempTuple = new Tuple
{
f = int.Parse(fields[0]),
l = int.Parse(fields[1]),
c = float.Parse(fields[2])
};
tuples.Add(tempTuple);
}
Dictionary<HashSet<int>, float> solutions = new Dictionary<HashSet<int>, float>();
for (int i = 0; i < tuples.Count; i++)
{
int f = F;
int l = L;
float c = 0;
HashSet<int> chosen = new HashSet<int>();
for (int j = i; j < tuples.Count; j++)
{
Tuple current = tuples[j];
bool anyUsed = false;
for (int k = current.f; k <= current.l; k++)
{
if (!w[k])
{
anyUsed = true;
w[k] = true;
}
}
if (anyUsed)
{
c += current.c;
chosen.Add(j);
}
bool allPainted = w.Values.All(r => r == true);
if (allPainted)
{
solutions.Add(chosen, c);
for (int m = F; m <= L; m++)
{
w[m] = false;
}
break;
}
}
}
}
struct Tuple
{
public int f;
public int l;
public float c;
def findCost(start, end, costs):
minsofar = -1
for idx, cost in enumerate(costs):
if cost[1] < start or cost[0] > start:
continue
currcost = None
if cost[1] >= end:
currcost = cost[2]
else:
if idx+1 < len(costs):
currcost = findCost(cost[1], end, costs[:idx] + costs[idx+1:])
if currcost is not None:
currcost += cost[2]
if minsofar == -1 or (currcost and minsofar > currcost):
minsofar = currcost
return minsofar
print(findCost(0, 5, [[0, 5, 10], [0, 4, 1], [0, 2,5], [2, 5, 1]]))
print(findCost(5, 10, [[0, 5, 10], [0, 4, 1], [0, 2,5], [2, 5, 1], [1, 11, 4]]))
print(findCost(0, 10, [[1, 5, 1], [0, 6, 2], [2, 8, 3], [5, 10, 1], [0, 11, 8]]))
print(findCost(0, 5, [[0, 5, 10], [0, 3, 1], [3, 4, 2], [3, 4, 1], [4, 5, 1], [0, 2, 5]]))
print(findCost(0, 5, [[1,4, 10], [2, 5, 6]]))
print(findCost(0, 5, [(0, 5, 10), (0, 4, 1), (0, 2, 5), (2, 5, 1)]))
print(findCost(0, 5, [(1, 4, 10), (2, 5, 6)]))
print(findCost(2, 6, []))
print(findCost(2, 6, [(3, 3, 1), (0, 8, 12), (2, 2, 1), (4, 6, 1)]))
Here is "expected" solution. (N*log(N) where N is number of intervals)
import heapq
def solve(first, last, intervals):
heap = [(0, first)]
for pos, end, cost in sorted(intervals + [(last, last, 0)]):
while heap and heap[0][1] < pos:
heapq.heappop(heap)
if not heap:
return -1
curCost, curPos = heap[0]
if curPos >= last:
return curCost
heapq.heappush(heap, (cost + curCost, end))
assert solve(0, 5, [[0, 5, 10], [0, 4, 1], [0, 2,5], [2, 5, 1]]) == 2
assert solve(0, 5, [[1,4, 10], [2, 5, 6]]) == -1
assert solve(0, 0, []) == 0
assert solve(0, 5, [[-3, -1, 10], [-1, 5, 10]]) == 10
Greedy solution approach:
1. Filter all Triples not fit for selection (not within range) - O(n)
2. Sort triples according to weight formula (num. uncovered range length + cost). Best options will be picked first - O(n logn)
3. Keep removing triples from list while full range not covered and while list not empty.
Total Time: - O(n log n)
public class MinCostPaint {
public static void main(String[] args) {
Range r = new Range(0,5);
Triple t1 = new Triple(0,5, 10);
Triple t2 = new Triple(0,4, 1);
Triple t3 = new Triple(0,2, 5);
Triple t4 = new Triple(2,5, 1);
List<Triple> list = new ArrayList<>();
list.add(t1);
list.add(t2);
list.add(t3);
list.add(t4);
findMinCostPaint(r, list);
Triple t2a = new Triple(1,4, 10);
Triple t2b = new Triple(2,5, 6);
List<Triple> list2 = new ArrayList<>();
list2.add(t2a);
list2.add(t2b);
findMinCostPaint(r, list2);
}
public static int findMinCostPaint(Range r, List<Triple> ts) {
List<Triple> tss = new ArrayList<>();
for (Triple triple : ts) {
if (triple.s >= r.s && triple.s < triple.e) {
tss.add(triple);
}
}
tss.sort(new TripleComparator(r));
List<Triple> result = new ArrayList<>();
Map<Integer, Boolean> paintedMap = new HashMap<>();
for (int i = r.s; i <= r.e; i++) {
paintedMap.put(i, Boolean.FALSE);
}
int paintedCount = 0;
int cost = 0;
while(!tss.isEmpty() && paintedCount < paintedMap.size()) {
Triple t = tss.remove(0);
for (int i = t.s; i <= t.e; i++) {
if (paintedMap.containsKey(i) && paintedMap.get(i).equals(Boolean.FALSE)) {
paintedMap.put(i, Boolean.TRUE);
paintedCount++;
}
}
cost += t.cost;
result.add(t);
}
if (paintedCount < paintedMap.size()) {
System.out.println("No possible ranges");
return -1;
}
for (Triple triple : result) {
System.out.println("(" + triple.s + "," + triple.e + ")");
}
System.out.println("min cost = " + cost);
return cost;
}
}
class TripleComparator implements Comparator<Triple> {
private Range rangeToCover;
public TripleComparator(Range rangeToCover) {
super();
this.rangeToCover = rangeToCover;
}
@Override
public int compare(Triple o1, Triple o2) {
Integer o1RangeUnCovered = (rangeToCover.e - o1.e) + (o1.s - rangeToCover.s);
if (o1RangeUnCovered < 0) {
o1RangeUnCovered = rangeToCover.e - rangeToCover.s;
}
Integer o2RangeUnCovered = (rangeToCover.e - o2.e) + (o2.s - rangeToCover.s);
if (o2RangeUnCovered < 0) {
o2RangeUnCovered = rangeToCover.e - rangeToCover.s;
}
Integer o1Weight = o1RangeUnCovered + o1.cost;
Integer o2Weight = o2RangeUnCovered + o2.cost;
return o1Weight.compareTo(o2Weight);
}
}
class Range {
Integer s;
Integer e;
public Range(int s, int e) {
super();
this.s = s;
this.e = e;
}
}
class Triple extends Range {
Integer cost;
public Triple(int s, int e, int cost) {
super(s, e);
this.cost = cost;
}
}
/**
output:
(0,4)
(2,5)
min cost = 2
No possible ranges
n is the number of intervals in input.
Time complexity of this implementation is O((n*logn)^2)
Can be optimized to O(n*n) by replacing std::map with an ordered-hash implementation.
Idea is to construct a cost_map.
For each interval <f, l> in input, insert key f and key l into cost_map.
cost_map[k] contains:
1) Adjacency vector = [<k,i> for all <k,i> in set of intervals]
2) Least cost to destination (initialized to infinity)
Traverse keys in cost_map from highest to lowest.
For each interval <k,last> in cost_map[k]
update cost_map[k]'s least_cost to destination.
For each i such that k < i <= last, update least_cost at cost_map[i]
cost_map[0]'s least_cost is the cost to the destination. If it is infinity, return -1.
typedef struct {
int first;
int last;
double cost;
} Triple;
typedef struct {
std::map<int, double> *adj_map;
double least_cost;
} AdjacentCosts;
AdjacentCosts *add_to_cost_map(std::map<int, AdjacentCosts*>& cost_map, int v)
{
AdjacentCosts *adj_costs_ptr = new AdjacentCosts();
adj_costs_ptr->adj_map = new std::map<int, double>();
adj_costs_ptr->least_cost = std::numeric_limits<double>::infinity();
cost_map[v] = adj_costs_ptr;
return adj_costs_ptr;
}
void build_cost_map(int first, int last, std::vector<Triple>& triples,
std::map<int, AdjacentCosts*>& cost_map)
{
// Build cost_map
std::vector<Triple>::iterator it;
add_to_cost_map(cost_map, first);
add_to_cost_map(cost_map, last);
for (it = triples.begin(); it != triples.end(); it++) {
AdjacentCosts *adj_costs_ptr;
std::map<int, AdjacentCosts*>::iterator cost_map_it = cost_map.find(it->first);
if (cost_map_it == cost_map.end()) {
// Insert triple's first if it doesn't exist
adj_costs_ptr = add_to_cost_map(cost_map, it->first);
} else {
adj_costs_ptr = cost_map_it->second;
}
// Insert triple's last if it doesn't exist
if (cost_map.find(it->last) == cost_map.end()) {
add_to_cost_map(cost_map, it->last);
}
std::map<int, double>& adj_map = *(adj_costs_ptr->adj_map);
std::map<int, double>::iterator adj_map_it = adj_map.find(it->last);
if (adj_map_it == adj_map.end()) {
adj_map[it->last] = it->cost;
} else {
adj_map[it->last] = std::min(adj_map[it->last], it->cost);
}
}
}
void solve(int first, int last, std::vector<Triple>& triples,
std::map<int, AdjacentCosts*>& cost_map)
{
// For each 'f' in cost_map
std::map<int, AdjacentCosts*>::reverse_iterator it;
for (it = cost_map.rbegin(); it != cost_map.rend(); it++) {
int f = it->first;
AdjacentCosts *adj_costs_ptr = it->second;
std::map<int, double>& adj_map = *(adj_costs_ptr->adj_map);
// For each {l, cost} in cost_map[f]
std::map<int, double>::reverse_iterator adj_it;
for (adj_it = adj_map.rbegin(); adj_it != adj_map.rend(); adj_it++) {
int l = adj_it->first;
double cost = adj_it->second;
double my_least_cost = adj_costs_ptr->least_cost;
if (l == last) {
my_least_cost = std::min(my_least_cost, cost);
} else {
my_least_cost = std::min(my_least_cost, cost + cost_map[l]->least_cost);
}
adj_costs_ptr->least_cost = my_least_cost;
// update least_cost in cost_map[k] for all f < k <= l
// TODO: Can interval trees help reduce time complexity here ?
std::map<int, AdjacentCosts*>::reverse_iterator cost_map_it;
for (cost_map_it = cost_map.rbegin();
(cost_map_it != cost_map.rend()) and cost_map_it->first > f;
cost_map_it++) {
if (cost_map_it->first > l)
continue;
AdjacentCosts& adj_costs = *(cost_map_it->second);
adj_costs.least_cost = std::min(my_least_cost, adj_costs.least_cost);
}
}
}
}
double min_cost(int first, int last, std::vector<Triple>& triples)
{
std::map<int, AdjacentCosts*> cost_map; // Key=first, Value=NeighborCost
build_cost_map(first, last, triples, cost_map);
solve(first, last, triples, cost_map);
double result = cost_map[first]->least_cost;
if (result == std::numeric_limits<double>::infinity()) {
result = -1;
}
return result;
}
In Perl
#!/usr/bin/perl -W
use strict;
print find_cost(0, 5, [[0, 5, 10], [0, 4, 1], [0, 2,5], [2, 5, 1]])."\n";
print find_cost(5, 10, [[0, 5, 10], [0, 4, 1], [0, 2,5], [2, 5, 1], [1, 11, 4]])."\n";
print find_cost(0, 10, [[1, 5, 1], [0, 6, 2], [2, 8, 3], [5, 10, 1], [0, 11, 8]])."\n";
print find_cost(0, 5, [[0, 5, 10], [0, 3, 1], [3, 4, 2], [3, 4, 1], [4, 5, 1], [0, 2, 5]])."\n";
print find_cost(0, 5, [[1,4, 10], [2, 5, 6]])."\n";
sub find_cost
{
my $first = shift;
my $last = shift;
my $triples = shift; # array reference
my $min_cost = -1;
for (my $i = 0; $i < scalar @{$triples}; $i++)
{
if ($triples->[$i]->[0] > $first || # Starts after first
$triples->[$i]->[1] < $first) # Ends before first
{
next;
}
my $cost = -1;
if ($triples->[$i]->[1] >= $last) # Ends after last, so add the cost
{
$cost = $triples->[$i]->[2];
}
else
{
if ($i < scalar @{$triples} - 1)
{
my @left = @{$triples}; # copy because splice is destructive.
my @right = @{$triples};# copy
my @newarray = (splice(@left, 0, $i), splice(@right, $i + 1));
$cost = find_cost($triples->[$i]->[1], $last, \@newarray);
$cost += $triples->[$i]->[2] if ($cost != -1);
}
}
$min_cost = $cost
if ($min_cost == -1 || ($cost != -1 && $min_cost > $cost));
}
return $min_cost;
}
My solution in Java:
F(first, last) = min{ (F(first, i) + F(i, last)) } (i : first+ 1 -> last). After that we need compare with min F(first, last) if (first, last) existed inside a range in input.
public class PrintCostPaint {
public static void main(String[] agrs) {
int[][] a = { { 0, 2, 5 }, { 0, 4, 1 }, { 0, 5, 10 }, { 2, 5, 1 } };
System.out.println(cost(0, 5, a));
}
private static int cost(int first, int last, int[][] input) {
int min = Integer.MAX_VALUE;
for (int i = 0; i < input.length; i++) {
if (last <= input[i][1] && first >= input[i][0]) {
if (min > input[i][2]) {
min = input[i][2];
}
}
}
if (last - first == 1) {
// if (min == Integer.MAX_VALUE)
return min;
}
int cost = min;
for (int i = first + 1; i < last; i++) {
int totalCost = sum(cost(first, i, input), cost(i, last, input));
if (cost > totalCost && totalCost > 0) {
cost = totalCost;
}
}
return cost == Integer.MAX_VALUE ? -1 : cost;
}
private static int sum(int a, int b) {
if (a == -1 || b == -1) {
return -1;
}
return a + b;
}
}
O(nlogn) time and O(2*n) space complexity solution Java:
class Node {
Node left;
Node right;
int a, b, val;
Node(int a, int b) {
this.a = a;
this.b = b;
this.val = -1;
}
}
Node buildTree(int a, int b) {
Node root = new Node(a,b);
if ( a != b ) {
root.left = buildTree( a, mid );
root.right = buildTree( mid + 1, b );
}
return root;
}
insertSegment(int a, int b, int cost, Node root) {
if ( root.a > b || root.b < a ) return;
if ( a <= root.a && b >= root.b ) {
if ( root.val == -1 || root.val > cost ) {
root.val = cost;
return;
}
}
insertSegment(a, b, cost, root.left, root.right);
insertSegment(a, b, cost, root.left, root.right);
if ( root.left.val != -1 && root.right.val != -1) {
if ( root.val == -1 || root.val > root.left.val + root.right.val ) {
root.val = root.left.val + root.right.val;
}
}
}
Node root = buildTree(0, 5);
insertSegment(0,5,10);
insertSegment(0,5,10);
insertSegment(0,5,10);
insertSegment(0,5,10);
insertSegment(0,5,10);
System.out.println(root.val);
#include <iostream>
#include <cstdio>
#include <climits>
#include <algorithm>
#include <queue>
#include <cstring>
#include <cmath>
#include <vector>
#include <list>
#include <stack>
#include <bitset>
#include <string>
#include <stack>
#include <set>
#include <map>
#include <deque>
#include <ctime>
#define lld long long
#define INF 10002
using namespace std;
struct interval{
int start,end,cost;
interval(){}
interval(int s,int e,int c){
start = s;
end = e;
cost = c;
}
bool contains(int key){
if(key>=start && key<=end)
return true;
else
return false;
}
};
int dp[INF];
int main(){
cin.sync_with_stdio(false);
cout.sync_with_stdio(false);
int start,end;
cin>>start>>end;
vector<interval> store;
int n;
cin>>n;
for(int i = 0;i<n;i++)
{
interval newInterval;
cin>>newInterval.start>>newInterval.end>>newInterval.cost;
store.push_back(newInterval);
}
dp[0] = INF;
for(int i = 0;i<n;i++){
if(store[i].contains(start))
dp[0] = min(dp[0],store[i].cost);
}
// cout<<dp[0]<<endl;
for(int i = start+1;i<=end;i++){
dp[i-start] = INF;
for(int j = 0;j<n;j++){
if(store[j].contains(i))
{
int cost = store[j].cost;
if(store[j].start>=start+1)
cost = cost + dp[store[j].start-start-1];
dp[i-start] = min(dp[i-start],cost);
}
}
}
//for(int i = 0;i<end-start+1;i++)
// cout<<dp[i]<<" ";
if(dp[end-start]>=INF)
cout<<"-1\n";
else
cout<<dp[end-start]<<endl;
return 0;
}
// RangePaint.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <vector>
class Cost {
public:
Cost(int begin, int end, float cost) :_begin(begin), _end(end), _cost(cost) {
}
int getBegin() {
return _begin;
}
int getEnd() {
return _end;
}
float getCost() {
return _cost;
}
private:
int _begin;
int _end;
float _cost;
};
float findMinCost(int begin, int end, const std::vector<Cost *>& costs) {
float * cumulativeCost;
cumulativeCost = new float[end-begin];
for (int i = begin; i<end;i++) {
cumulativeCost[i] = -1;
}
std::vector<Cost *>::const_iterator itr = costs.cbegin();
while (itr != costs.cend())
{
float startCost = 0;
if((*itr)->getBegin() > begin){
if(cumulativeCost[(*itr)->getBegin() - begin] == -1) {
itr++;
continue;
}
startCost = cumulativeCost[(*itr)->getBegin() - begin];
}
for (int j = (*itr)->getBegin(); j <(*itr)->getEnd(); ++j) {
if( j - begin >= 0 && j < end && ( cumulativeCost[j - begin] == -1 || cumulativeCost[j - begin] > (startCost + (*itr)->getCost())) ) {
cumulativeCost[j - begin] = startCost + (*itr)->getCost();
}
}
++itr;
}
return cumulativeCost[end - begin - 1];
}
int _tmain(int argc, _TCHAR* argv[])
{
std::vector<Cost *> costs;
costs.push_back(new Cost(0,5,10));
costs.push_back(new Cost(0,4,1));
costs.push_back(new Cost(0,2,5));
costs.push_back(new Cost(2,5,1));
//costs.push_back(new Cost(1,4,10));
//costs.push_back(new Cost(2,5,6));
float minCost = findMinCost(0, 5, costs);
printf("Min Cost = %f", minCost);
getchar();
return 0;
}
Time complexity Min{ mlogm, n} where m in number of ranges and n is the end range
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
public class MinimumCost {
private int INT_MAX = 999999999;
public static void main(String[] args) {
MinimumCost obj = new MinimumCost();
List<Range> ranges = new ArrayList<>();
ranges.add(obj.createRange(0, 1, 1.0));
ranges.add(obj.createRange(1, 2, 1.0));
ranges.add(obj.createRange(2, 4, 2.0));
ranges.add(obj.createRange(2, 5, 3.0));
ranges.add(obj.createRange(1, 3, 1.0));
ranges.add(obj.createRange(0, 2, 2.0));
ranges.add(obj.createRange(3, 5, 2.0));
System.out.println(obj.findMinimumCostToPaint(5, ranges));
}
public Range createRange(int start, int end, double cost) {
return new Range(start, end, cost);
}
public class Range {
private int start;
private int end;
private double cost;
public Range(int start, int end, double cost) {
this.start = start;
this.end = end;
this.cost = cost;
}
public int getStart() {
return start;
}
public int getEnd() {
return end;
}
public double getCost() {
return cost;
}
}
public class RangeComparator implements Comparator<Range> {
@Override
public int compare(Range o1, Range o2) {
if (o1.getStart() == o2.getStart()) {
return Integer.compare(o1.getEnd(), o2.getEnd());
}
return Integer.compare(o1.getStart(), o2.getEnd());
}
}
public double findMinimumCostToPaint(int n, List<Range> ranges) {
double[] result = new double[n + 1];
for (int i = 1; i <= n; i++) {
result[i] = INT_MAX;
}
result[0] = 0;
Collections.sort(ranges, new RangeComparator());
for (Range r : ranges) {
double temp = result[r.getStart()] + r.getCost();
if (temp < result[r.getEnd()]) {
result[r.getEnd()] = temp;
}
}
if (result[n] == INT_MAX) {
return -1;
}
return result[n];
}
}
This solution iterates thourgh all combinations of quote triplets. For each triplet, either it is included in final solution, or it is not. The solution evaluates both paths for each triplet and comes up with a minimum cost solution.
typedef struct {
int f;
int l;
double c;
} quote;
typedef struct {
int f;
int l;
} range;
quote add(quote q1, quote q2) {
if ((q1.f <= q2.f) && (q1.l >= q2.l))
return q1;
if ((q1.f >= q2.f) && (q1.l <= q2.l))
return q2;
// ranges are not inclusive of each other
quote result;
result.f = (q1.f < q2.f) ? q1.f : q2.f;
result.l = (q1.l > q2.l) ? q1.l : q2.l;
result.c = q1.c + q2.c;
return result;
}
double min_cost(quote q[], unsigned int n, range r) {
if ((n == 0) || (r.f > r.l))
return -1;
quote p;
p.f = r.l;
p.l = r.f;
p.c = 0;
return get_min_cost(q, n, r, p);
}
double get_min_cost(quote q[], unsigned int n, range r, quote p) {
if (n == 0)
return -1;
if ((p.f <= r.f) && (p.l >= r.l))
return p.c;
double c1 = get_min_cost(q + 1, n - 1, r, p);
double c2 = get_min_cost(q + 1, n - 1, r, add(p, q[0]));
if (c1 == -1)
return c2;
if (c2 == -1)
return c1;
return (c1 < c2) ? c1 : c2;
}
public class Solution {
public static void main(String [] args) {
Triples t1 = new Triples(0, 5, 10);
Triples t2 = new Triples(0, 4, 1);
Triples t3 = new Triples(0, 2, 5);
Triples t4 = new Triples(2, 5, 1);
Triples [] array = {t1, t2, t3, t4};
System.out.println(getCost(0, 5, array));
}
public static int getCost(int start, int end, Triples [] array) {
int sum = 0;
int index = 0;
Arrays.sort(array);
while (index <= end) {
boolean found = false;
for (int i = 0; i < array.length; i++) {
if (array[i].isInclude(index)) {
sum += array[i].cost;
index = array[i].end + 1;
found = true;
break;
}
}
if (!found) {
return -1;
}
}
return sum;
}
}
class Triples implements Comparable<Triples> {
final int start;
final int end;
final int cost;
public Triples(int start, int end, int cost) {
this.start = start;
this.end = end;
this.cost = cost;
}
@Override
public int compareTo(Triples o) {
if (this.cost == o.cost) {
return Integer.compare(this.start, o.end);
}
return Integer.compare(this.cost, o.cost);
}
public boolean isInclude(int index) {
return index <= this.end && index >= this.start;
}
}
public class Painter {
static class Interval implements Comparable {
int beg;
int end;
int cost;
public Interval(int beg, int end, int cost) {
this.beg = beg;
this.end = end;
this.cost = cost;
}
public int compareTo(Object o) {
Interval i = (Interval) o;
if (i.beg != this.beg) return this.beg - i.beg;
else return this.end - i.end;
}
public String toString() {
return "(" + this.beg + "," + this.end + "," + this.cost + ")";
}
}
// intervals must be sorted before using this method
static int minCost(int beg, int end, Interval[] intervals, int idx, int costSoFar) {
if (beg >= end) return costSoFar;
if (idx == intervals.length || beg < intervals[idx].beg) return Integer.MAX_VALUE;
if (beg > intervals[idx].end) return minCost(beg, end, intervals, idx + 1, costSoFar);
int costUsingIdx = minCost(intervals[idx].end, end, intervals, idx + 1, costSoFar + intervals[idx].cost);
int costWithoutIdx = minCost(beg, end, intervals, idx + 1, costSoFar);
return costUsingIdx < costWithoutIdx ? costUsingIdx : costWithoutIdx;
}
static void test(int beg, int end, Interval[] intervals) {
int minCost = minCost(beg, end, intervals, 0, 0);
System.out.println("min cost = " + minCost);
System.out.println("---------------------------");
}
public static void main(String[] args) {
Interval[] intervals1 = new Interval[] {new Interval(0,5,10), new Interval(0,4,1), new Interval(0,2,5), new Interval(2,5,1)};
Arrays.sort(intervals1);
test(0, 5, intervals1);
Interval[] intervals2 = new Interval[] {new Interval(2, 5, 6), new Interval(1,4, 10)};
Arrays.sort(intervals2);
test(0, 5, intervals2);
}
}
from itertools import combinations
def check_range(lb, ub, paint):
sets = set()
for i in xrange(len(lb)):
sets |= set(range(max(lb[i],paint[0]),\
min(ub[i],paint[1]) + 1))
if len(sets) == paint[1] - paint[0] + 1:
return True
else:
False
def minimize_cost(paint, costs):
min_cost = None
for i in xrange(1, len(costs) + 1):
for c in combinations(costs, i):
lb, ub, cost = zip(*c)
if check_range(lb, ub, paint):
cost_sum = sum(cost)
if not min_cost or min_cost > cost_sum:
min_cost = cost_sum
return min_cost
paint = [0, 5]
costs = [(0, 5, 10), (0, 4, 1), (0, 2,5), (2, 5, 1)]
print minimize_cost(paint, costs)
dynamic programming O(n^2)
- EPavlova June 07, 2016class Range implements Comparable<Range>{ private int l; private int r; private double cost; public Range(int i, int j, int k) { l = i; r = j; cost = k; } @Override public int compareTo(Range obj) { if (r == obj.r) { return obj.l - l; } return r - obj.r; } } double minCost(Range[] ranges, int L, int R) { Arrays.sort(ranges); double[] dp = new double[R + 1]; for (int j = L + 1; j <= R; j++) { double min = Double.MAX_VALUE; int i = ranges.length - 1; while ( i >= 0 && ranges[i].r >= j) { if (ranges[i].l < j) { if (dp[ranges[i].l] != -1 && dp[ranges[i].l] + ranges[i].cost < min) { min = dp[ranges[i].l] + ranges[i].cost; } } i--; } if (min == Double.MAX_VALUE) { dp[j] = -1; } else dp[j] = min; } return dp[R]; }