Dilpreet wants to paint his dog's home that has n boards with different lengths. The length of i^{th }board is given by arr[i] where arr[] is an array of n integers. He hired k painters for this work and each painter takes 1 unit time to paint 1 unit of the board. 
The problem is to find the minimum time to get this job done if all painters start together with the constraint that any painter will only paint continuous boards, say boards numbered {2,3,4} or only board {1} or nothing but not boards {2,4,5}.
Example 1:
Input:
n = 5
k = 3
arr[] = {5,10,30,20,15}
Output: 35
Explanation: The most optimal way will be:
Painter 1 allocation : {5,10}
Painter 2 allocation : {30}
Painter 3 allocation : {20,15}
Job will be done when all painters finish
i.e. at time = max(5+10, 30, 20+15) = 35
Example 2:
Input:
n = 4
k = 2
arr[] = {10,20,30,40}
Output: 60
Explanation: The most optimal way to paint:
Painter 1 allocation : {10,20,30}
Painter 2 allocation : {40}
Job will be complete at time = 60
Your task:
Your task is to complete the function minTime() which takes the integers n and k and the array arr[] as input and returns the minimum time required to paint all partitions.
Expected Time Complexity: O(n log m) , m = sum of all boards' length
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ n ≤ 10^{5}
1 ≤ k ≤ 10^{5}
1 ≤ arr[i] ≤ 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Sorting

Divide and conquer

Complete search

Starter code: #User function Template for python3

class Solution:
    def minTime (self, arr, n, k):
        #code here
        

Solutions:
class Solution:

	def minTime(self, arr, n, k):

		def numofPainter(maxLen):
			painters = 1
			total = 0
			for board in arr:
				total += board
				if total > maxLen:
					total = board
					painters += 1
			return painters
		(low, high) = (max(arr), sum(arr))
		while low < high:
			p = low + (high - low) // 2
			curr_painters = numofPainter(p)
			if curr_painters <= k:
				high = p
			else:
				low = p + 1
		return low


class Solution:

	def minTime(self, arr, n, k):

		def numOfPainter(maxLen):
			painters = 1
			total = 0
			for board in arr:
				total += board
				if total > maxLen:
					total = board
					painters += 1
			return painters
		(low, high) = (max(arr), sum(arr))
		while low < high:
			pivot = low + (high - low) // 2
			currPainters = numOfPainter(pivot)
			if currPainters <= k:
				high = pivot
			else:
				low = pivot + 1
		return low


class Solution:

	def numberOfPainters(self, arr, n, maxLen):
		total = 0
		numPainters = 1
		for i in arr:
			total += i
			if total > maxLen:
				total = i
				numPainters += 1
		return numPainters

	def minTime(self, arr, n, k):
		lo = max(arr)
		hi = sum(arr)
		while lo < hi:
			mid = lo + (hi - lo) // 2
			requiredPainters = self.numberOfPainters(arr, n, mid)
			if requiredPainters <= k:
				hi = mid
			else:
				lo = mid + 1
		return lo


class Solution:

	def ifpossible(self, arr, n, k, mid):
		load = 0
		painter = 1
		for board in arr:
			load += board
			if load > mid:
				painter += 1
				load = board
		return painter <= k

	def recursion(self, arr, n, k, start, end, ans):
		if start > end:
			return ans
		mid = (start + end) // 2
		output = self.ifpossible(arr, n, k, mid)
		if output:
			ans = mid
			end = mid - 1
			return self.recursion(arr, n, k, start, end, ans)
		else:
			start = mid + 1
			return self.recursion(arr, n, k, start, end, ans)

	def minTime(self, arr, n, k):
		(start, end) = (max(arr), sum(arr))
		ans = -1
		return self.recursion(arr, n, k, start, end, ans)


class Solution:

	def isPossible(arr, n, k, mid):
		time_sum = 0
		painter_count = 1
		for i in range(n):
			if time_sum + arr[i] <= mid:
				time_sum += arr[i]
			else:
				painter_count += 1
				if painter_count > k or arr[i] > mid:
					return False
				time_sum = arr[i]
		return True

	def minTime(self, arr, n, k):
		low = 0
		high = sum(arr)
		mid = int(low + (high - low) / 2)
		ans = -1
		while low <= high:
			if Solution.isPossible(arr, n, k, mid):
				ans = mid
				high = mid - 1
			else:
				low = mid + 1
			mid = int(low + (high - low) / 2)
		return ans


class Solution:

	def minTime(self, arr, n, k):
		s = 0
		sumi = 0
		ans = -1
		for i in arr:
			sumi = sumi + i
		e = sumi
		mid = (s + e) // 2
		while s <= e:
			if n == 1:
				return arr[0]
			if self.ispossible(arr, n, k, mid):
				ans = mid
				e = mid - 1
			else:
				s = mid + 1
			mid = (s + e) // 2
		return ans

	def ispossible(self, arr, n, k, mid):
		sc = 1
		ps = 0
		for i in range(len(arr)):
			if ps + arr[i] <= mid:
				ps += arr[i]
			else:
				sc += 1
				if sc > k or arr[i] > mid:
					return False
				ps = arr[i]
		return True


def isValid(mid, arr, n, k):
	sum_ = 0
	count = 1
	for i in arr:
		sum_ += i
		if sum_ > mid:
			count += 1
			sum_ = i
			if count > k:
				return False
	return True

class Solution:

	def minTime(self, arr, n, k):
		(l, r) = (max(arr), sum(arr))
		while l <= r:
			mid = l + (r - l) // 2
			if isValid(mid, arr, n, k):
				r = mid - 1
			else:
				l = mid + 1
		return l


class Solution:

	def minTime(self, arr, n, k):
		l = 0
		r = 0
		for i in range(len(arr)):
			r = r + arr[i]
		mid = l + (r - l) // 2
		ans = -1

		def ispossible(mid, arr, k):
			pc = 1
			cs = 0
			for i in range(len(arr)):
				if cs + arr[i] <= mid:
					cs = cs + arr[i]
				else:
					pc = pc + 1
					if pc > k or arr[i] > mid:
						return False
					cs = arr[i]
			return True
		while l <= r:
			mid = l + (r - l) // 2
			if ispossible(mid, arr, k):
				ans = mid
				r = mid - 1
			else:
				l = mid + 1
		return ans


class Solution:

	def minTime(self, arr, n, k):
		sum = 0
		for i in arr:
			sum += i
		low = 0
		high = sum
		mid = (low + high) // 2
		ans = -1
		while low <= high:
			if possible(arr, n, k, mid):
				ans = mid
				high = mid - 1
			else:
				low = mid + 1
			mid = (low + high) // 2
		return ans

def possible(arr, n, k, mid):
	c = 1
	sum = 0
	for i in range(n):
		if sum + arr[i] <= mid:
			sum = sum + arr[i]
		else:
			sum = arr[i]
			c = c + 1
			if c > k or arr[i] > mid:
				return False
	return True