Programming/painters partition.cpp at master · arshdeep/Programming · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <climits>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>
using namespace std;

int sum(int *vect, int s, int e)
{
	int sum = 0;

	for (int i = s; i < e; ++i)
	{
		sum += vect[i];
	}

	return sum;
}
// exponential time complexity
int partition(int *arr, int n, int k)
{
	if (k == 1) return sum(arr, 0, n);
	if (n == 1) return arr[0];
	int min = INT_MAX;
	int max = INT_MAX;
	for (int i = 1; i < n; ++i)
	{
		int rsum = sum(arr, i, n);
		int lsum = partition(arr, i, k - 1);

		max = std::min(max, std::max(rsum, lsum));
	}
	return max;
}

// time : O(k * n ^ 2), space : O(nk)
int partitionDP(int *arr, int n, int k)
{
	vector<vector<int>> dp(n + 1, vector<int>(k+1));
	vector<int> csum(n+1);

	for (int i = 1; i <= n; ++i)
	{
		csum[i] = csum[i - 1] + arr[i-1];
	}

	for(int i = 1; i <= n; ++i)
	{
		dp[i][1] = csum[i];
	}

	for (int kk = 1; kk <= k; ++kk)
	{
		dp[1][kk] = arr[0];
	}

	for (int kk = 2; kk <= k; ++kk)
	{
		for (int i = 2; i <= n; ++i)
		{
			int best = INT_MAX;
			for (int j = 1; j <= i; ++j)
			{
				best = std::min(best, std::max(dp[j][kk-1], csum[i] - csum[j]));
			}
			dp[i][kk] = best;
		}
	}
	return dp[n][k];
}

// geedy approach O(n*SUM) ref: tocoder
int getMostWork( int *folders, int n, int workers ) {
   int lo = *max_element(folders, folders+n);
   int hi = accumulate(folders, folders+n, 0 );

   while ( lo < hi ) {
      int x = lo + (hi-lo) / 2;

      int required = 1, current_load = 0;
      for ( int i=0; i<n; ++i ) {
         if ( current_load + folders[i] <= x ) {
            // the current worker can handle it
            current_load += folders[i];
         }
         else {
            // assign next worker
            ++required;
            current_load = folders[i];
		 }
      }

      if ( required <= workers )
         hi = x;
      else
         lo = x+1;
   }

   return lo;
}

int main(int argc, char *argv[])
{
	int a[] = {10, 20, 30, 40, 50, 60, 70, 80, 90};
	int size = sizeof(a)/sizeof(a[0]);
	cout<<getMostWork(a, size, 3)<<endl;

	cout<<getMostWork(a, size, 5)<<endl;

	int a2[] = { 950, 650, 250, 250, 350, 100, 650, 150, 150, 700 };
	size = sizeof(a2)/sizeof(a2[0]);
	cout<<partitionDP(a2, size, 6)<<endl;

	int a3[] = { 568, 712, 412, 231, 241, 393, 865, 287, 128, 457, 238, 98, 980, 23, 782};
	size = sizeof(a3)/sizeof(a3[0]);
	cout<<partitionDP(a3, size, 4);

	getchar();
   return 0;
}