CareerCup

Thanks for sharing !
Here you have done is split in two cases:
- If two intervals do not intersect,then either consider it or do not consider it
- If they intersect,then without considering

Please let me know if I understood your logic right.
Also , time complexity will be 2^n of recursive algo, right?

public class BestDeal{

     public static void main(String []args){
        int [][] IntervalList = {{1,2},{2,4},{4,8}};
        int [] IntervalPrice = {10, 30, 25};
        int MaxPrice = 0;
        int bestDeal =0;
        for (int i=0 ;i< IntervalList.length; i++)
        if (MaxPrice < IntervalPrice[i]/(IntervalList[i][1]-IntervalList[i][0]))
        {
            MaxPrice=IntervalPrice[i]/(IntervalList[i][1]-IntervalList[i][0]);
        bestDeal=i;
        }
        
        
        System.out.println("BestDeal = " + IntervalList[bestDeal][0] + "," + IntervalList[bestDeal][1]);
     }
};

static int memo[];
	public static boolean intersect(Interval i2, Interval i1){
		return i2.s >= i1.s && i2.s <= i1.e;
	}
	public static int maxPrice(int i, Interval[] in, int last,int[] prices) {
		if(i >= in.length)
			return 0;
		
		if(memo[last] != -1)return memo[last];
		if(intersect(in[i], in[last])){
			return memo[last] = maxPrice(i + 1, in, last, prices);
		}
		return memo[last] = Math.max(prices[i] + maxPrice(i + 1, in, i, prices), maxPrice(i + 1, in, last, prices));
	}

	public static int maxPrice(Interval[] in, int[] prices) {
		memo = new int[prices.length];
		Arrays.fill(memo, -1);
		return maxPrice(0, in, 0,prices);
	}

public static void main(String[] args) {
		Solution s = new Solution();
		Interval []in = {s.new Interval(0, 0), s.new Interval(1, 3), s.new Interval(2, 3), s.new Interval(3, 5)};
		int[]p = {0, 2,10,5};
		
		System.out.println(maxPrice(in, p));
}

memo = new int[p.length];
		memo[0] = p[0];
		for(int i = 1; i < p.length; i++){
			for(int j = i - 1; j >= 0; j--){
				if(intersect(in[i],in[j])){
					memo[i] = Math.max(memo[i], p[i]);
				}else{
					memo[i] = Math.max(memo[i], memo[j] + p[i]);
				}
			}
		}

I think you are over complicating the problem. Why not simply look for the best:

function selectRenter($offers) {
	$maxIndex = -1;
	$maxProfit = 0;
	foreach($offers => $offer as $details) {
		$s = $details[0];
		$e = $details[1];
		$p = $details[2];
		if($p * ($e - $s + 1) > $maxProfit) {
			$maxProfit = $p * ($e - $s + 1);
			$maxIndex = $offer;
		}
	}
	return $maxIndex;
}

@Ankita

Yes, This what the solutions do.

The complexity is O(N^2) because the array memo caches the already calculated result.

Isn't this just a variation of best time to sell stock given input array that contains startring prices?

You can do it in n*log(n)

in python considering time intersection

def sort_by_start_date(arr):
return sorted(arr, key=lambda x: x[0]) # first idx is start date


def max_profit(requests):
global stacks, moneys

requests = sort_by_start_date(requests)

stacks = []
moneys = [] # should match number of stacks
max_money = requests[0][-1]
max_money_idx = 0
for start, end, money in requests:

time = start # current time is the start date

# initialisation
if len(stacks) == 0:
stacks.append([( start, end, money )])
moneys.append( money )
continue

# we loop through each scenario
for i in range(len(stacks)):
stack = stacks[i]
# see whether we can push this chunk into the stack
prev_start, prev_end, prev_money = stack[-1]

#print("here", time, end, money)
#print(prev_start, prev_end, prev_money)
#print(stacks)

if prev_end < time : # strictly less than
stack.append(( start, end, money ))
moneys[i] += money

# keep track of max money
if moneys[i] > max_money:
max_money = moneys[i]
max_money_idx = i

else: # this means it is a new scenario
# but there is a case we should not consider
# which is new block finishes after existing block
# with less money
if end >= prev_end and money <= prev_money:
continue # we discard this

# in this case we will need to create a new stack
# to keep track of new scenario
# new_stack = [ item for item in stacks[:-1] ] # last block is conflict -> not true could be multiple

# copy only those that dont conflict, ie end date < time
new_stack = [ item for item in stack if item[-1] < time ]

new_money = moneys[i] - prev_money + money
new_stack.append(( start, end, money ))
stacks.append(new_stack)
moneys.append(new_money)

# keep track of max money
if new_money > max_money:
max_money = new_money
max_money_idx = len(stacks)-1 # last index after appending

for money, stack in zip(moneys, stacks):
print("$%d"% money, stack )

return max_money, stacks[max_money_idx]




requests = [
(1, 10, 10),
(2,3, 2),
(7,10,8),
(1,3,5),
(8,10,7),
(4,6,8)
]

print (max_profit(requests))

using n stacks to store each scenario

public class BestDeal{

public static void main(String []args){
int [][] IntervalList = {{1,2},{2,4},{4,8}};
int [] IntervalPrice = {10, 30, 25};
int MaxPrice = 0;
int bestDeal =0;
for (int i=0 ;i< IntervalList.length; i++)
if (MaxPrice < IntervalPrice[i]/(IntervalList[i][1]-IntervalList[i][0]))
{
MaxPrice=IntervalPrice[i]/(IntervalList[i][1]-IntervalList[i][0]);
bestDeal=i;
}


System.out.println("BestDeal = " + IntervalList[bestDeal][0] + "," + IntervalList[bestDeal][1]);
}
};

""
THIS IMPLEMENTATION IS JUST A PYTHON VERSION OF AN OLDER POST WITH SOME EXPLANATION

Input: Two arrays. One for interval and other for the price of each interval.

Compute: We need to find the best value for the time duration we rent out the car, such that
there is no intersection between the time intervals. For simplicity I have just use discrete time interval with no overlap.

""

def bestDeal():
## [s,e]
interval = ((1,2),(2,4),(4,10))
price_interval = (30,20,100)
max_price = 0
best_interval = 0
for i in range(0,len(interval)):
price_comp = price_interval[i]/(interval[i][-1] - interval[i][0])
if max_price < price_comp:
max_price = price_comp
best_interval = i
print('Best Interval',interval[i],'at $',price_interval[i])

This is a classic problem on weighted interval scheduling problem. It is based on Dynamic Programming.