Yuckdonald%u2019s is considering opening a series of restaurants along Quaint Va

Question

Yuckdonald%u2019s is considering opening a series of restaurants along Quaint Valley Highway (QVH). The n possible locations are along a straight line, and the distances of these locations from the start of the QVH are, in miles and in increasing order m_1,m_2...m_n.
The constraints are as follows: At each location, Yuckdonald%u2019s may open at most restaurant. The expected profit from opening a restaurant at location i is p_i , where p_i>0
and i= 1,2...n
Any two restaurants should be at least k miles apart, where k is a positive integer. Give an efficient algorithm to compute the maximum expected total profit subject to the given constrain. Include run time analysis.
Yuckdonald%u2019s is considering opening a series of restaurants along Quaint Valley Highway (QVH). The n possible locations are along a straight line, and the distances of these locations from the start of the QVH are, in miles and in increasing order m_1,m_2...m_n.
The constraints are as follows: At each location, Yuckdonald%u2019s may open at most restaurant. The expected profit from opening a restaurant at location i is p_i , where p_i>0
and i= 1,2...n
Any two restaurants should be at least k miles apart, where k is a positive integer. Give an efficient algorithm to compute the maximum expected total profit subject to the given constrain. Include run time analysis.

Explanation / Answer

proposed algorithm :

step 1:

for i in 1 to n

R_i = j , such that p_j = maximum m_l which is <= m_i - k ; l = 1 to i

i.e. R_i = index of location which is closest to m_i - k

so, R_1 = 0

step 2:

for i = 1 to n

P_i = maximum profit obtained upto location i

= max(P_(i-1) , P_(R_i) + p_i)

run time analysis :

Step 1 will be calculated for each i . Also calculation of R_i will take log(n) time using binary search technique. So, it will take nlog(n)

Step 2 will also iterate for n times. But each P_i calcualtion will take constant time. So, it will take linear time.

Therefore, overall running time = O(nlog(n))

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.