Cloud Computing Platform You are managing a cloud...

python
def schedule(n,timeWindow,initial,regenRate,regenInterval,tasks):
    from collections import deque,defaultdict
    # tasks list of dict {profit,duration,resources,deps}
    indeg=[0]*n
    children=defaultdict(list)
    for i,t in enumerate(tasks):
        for d in t['deps']:
            indeg[i]+=1
            children[d].append(i)
    # ready tasks min-heap negative profit?
    import heapq
    ready=[]
    for i in range(n):
        if indeg[i]==0:
            heapq.heappush(ready,(-tasks[i]['profit'], i))
    time=0
    energy=initial
    maxCap=initial+regenRate
    nextRegen=regenInterval if regenInterval>0 else None
    totalProfit=0
    done=0
    while time<timeWindow and (ready or done<n):
        # choose task
        best=None
        temp=[]
        while ready:
            p_neg,i=heapq.heappop(ready)
            if tasks[i]['resources']<=energy:
                best=i
                break
            else:
                temp.append((p_neg,i))
        for item in temp:
            heapq.heappush(ready,item)
        if best is None:
            # no task can start now. advance to next regen
            if nextRegen is None:
                break
            if nextRegen<=time:
                nextRegen=time - (time%regenInterval)+regenInterval
            if nextRegen>timeWindow:
                break
            time=nextRegen
            energy=min(maxCap, energy+regenRate)
            nextRegen+=regenInterval
            continue
        # run task
        task=tasks[best]
        if time+task['duration']>timeWindow:
            continue # cannot fit, skip this task
        energy-=task['resources']
        # compute regen events during duration
        if regenInterval>0 and regenRate>0:
            regenEvents= ( (time+task['duration'])//regenInterval - time//regenInterval )
            energy=min(maxCap, energy+regenEvents*regenRate)
            # update nextRegen variable
            if nextRegen is not None:
                while nextRegen<=time:
                    nextRegen+=regenInterval
                while nextRegen<=time+task['duration']:
                    nextRegen+=regenInterval
        # task release
        energy=min(maxCap, energy+task['resources'])
        time+=task['duration']
        totalProfit+=task['profit']
        done+=1
        # update indegrees
        for child in children[best]:
            indeg[child]-=1
            if indeg[child]==0:
                heapq.heappush(ready,(-tasks[child]['profit'], child))
    return totalProfit

# test sample1
n=5; timeWindow=20; initial=2; regenRate=2; regenInterval=5
tasks=[]
tasks.append({'profit':80,'duration':4,'resources':2,'deps':[]})
tasks.append({'profit':70,'duration':3,'resources':1,'deps':[]})
tasks.append({'profit':60,'duration':6,'resources':2,'deps':[]})
tasks.append({'profit':60,'duration':2,'resources':1,'deps':[]})
tasks.append({'profit':100,'duration':6,'resources':2,'deps':[]})
print(schedule(n,timeWindow,initial,regenRate,regenInterval,tasks))

python
def schedule_debug():
    n=5; timeWindow=20; initial=2; regenRate=2; regenInterval=5
    tasks=[{'profit':80,'duration':4,'resources':2,'deps':[]},
           {'profit':70,'duration':3,'resources':1,'deps':[]},
           {'profit':60,'duration':6,'resources':2,'deps':[]},
           {'profit':60,'duration':2,'resources':1,'deps':[]},
           {'profit':100,'duration':6,'resources':2,'deps':[]}]
    from collections import defaultdict
    indeg=[0]*n
    children=defaultdict(list)
    ready=[(-t['profit'],i) for i,t in enumerate(tasks)]
    import heapq
    heapq.heapify(ready)
    time=0; energy=initial; maxCap=initial+regenRate; nextRegen=regenInterval
    total=0
    while time<timeWindow and ready:
        p,i=heapq.heappop(ready)
        if tasks[i]['resources']>energy:
            # wait
            while energy<tasks[i]['resources'] and time<timeWindow:
                time+=(nextRegen-time%regenInterval) if time%regenInterval>0 else regenInterval
                if time>timeWindow: break
                energy=min(maxCap,energy+regenRate)
            if time>timeWindow or energy<tasks[i]['resources']: continue
        if time+tasks[i]['duration']>timeWindow:
            continue
        energy-=tasks[i]['resources']
        # regen events
        regenEvents= ( (time+tasks[i]['duration'])//regenInterval - time//regenInterval )
        energy=min(maxCap, energy+regenEvents*regenRate)
        energy=min(maxCap,energy+tasks[i]['resources'])
        time+=tasks[i]['duration']
        total+=-p
        print('Start',i,'profit',-p,'time',time,'energy',energy)
    print('total',total)
schedule_debug()

python
def schedule2(prior='ratio'):
    n=5; timeWindow=20; initial=2; regenRate=2; regenInterval=5
    tasks=[{'profit':80,'duration':4,'resources':2,'deps':[]},
           {'profit':70,'duration':3,'resources':1,'deps':[]},
           {'profit':60,'duration':6,'resources':2,'deps':[]},
           {'profit':60,'duration':2,'resources':1,'deps':[]},
           {'profit':100,'duration':6,'resources':2,'deps':[]}]
    import heapq
    time=0; energy=initial; maxCap=initial+regenRate; nextRegen=regenInterval
    ready=list(range(5))
    scheduled=[]
    while time<timeWindow and ready:
        # choose candidate that fits timewindow and energy
        best=None; bestScore=None
        for idx in ready:
            if tasks[idx]['resources']<=energy and time+tasks[idx]['duration']<=timeWindow+1:
                if prior=='ratio':
                    score= -tasks[idx]['profit']/tasks[idx]['duration']
                elif prior=='profit':
                    score=-tasks[idx]['profit']
                elif prior=='duration':
                    score=tasks[idx]['duration']
                else:
                    score=0
                if best is None or score<bestScore:
                    best=idx; bestScore=score
        if best is None:
            # wait regen
            if time%regenInterval==0:
                time+=1  # wait one unit
            else:
                time += regenInterval - (time%regenInterval)
            if time>timeWindow: break
            energy=min(maxCap,energy+regenRate)
            continue
        ready.remove(best)
        energy-=tasks[best]['resources']
        regenEvents=( (time+tasks[best]['duration'])//regenInterval - time//regenInterval )
        energy=min(maxCap, energy+regenEvents*regenRate)
        energy=min(maxCap, energy+tasks[best]['resources'])
        time+=tasks[best]['duration']
        scheduled.append(best)
    profit=sum(tasks[i]['profit'] for i in scheduled)
    return profit,scheduled

print(schedule2('ratio'))

python
def schedule_resource():
    n=5; timeWindow=20; initial=2; regenRate=2; regenInterval=5
    tasks=[{'profit':80,'duration':4,'resources':2,'deps':[]},
           {'profit':70,'duration':3,'resources':1,'deps':[]},
           {'profit':60,'duration':6,'resources':2,'deps':[]},
           {'profit':60,'duration':2,'resources':1,'deps':[]},
           {'profit':100,'duration':6,'resources':2,'deps':[]}]
    ready=list(range(n))
    time=0;energy=initial;maxCap=initial+regenRate
    nextRegen=regenInterval
    scheduled=[]
    while time<=timeWindow and ready:
        candidates=[i for i in ready if tasks[i]['resources']<=energy and time+tasks[i]['duration']<=timeWindow+1]
        if not candidates:
            # wait regen
            if nextRegen<=time:
                nextRegen=time - (time%regenInterval)+regenInterval
            if nextRegen>timeWindow: break
            time=nextRegen
            energy=min(maxCap,energy+regenRate)
            nextRegen+=regenInterval
            continue
        # choose ascending resources then highest profit
        candidates.sort(key=lambda i:(tasks[i]['resources'], -tasks[i]['profit']))
        i=candidates[0]
        ready.remove(i)
        energy-=tasks[i]['resources']
        regenEvents=( (time+tasks[i]['duration'])//regenInterval - time//regenInterval )
        energy=min(maxCap, energy+regenEvents*regenRate)
        energy=min(maxCap, energy+tasks[i]['resources'])
        time+=tasks[i]['duration']
        scheduled.append(i)
    profit=sum(tasks[i]['profit'] for i in scheduled)
    return profit,scheduled
schedule_resource()


(370, [1, 3, 4, 0, 2])

python
def schedule_startConstraint():
    timeWindow=20
    initial=2; regenRate=2; regenInterval=5
    tasks=[{'profit':80,'duration':4,'resources':2},
           {'profit':70,'duration':3,'resources':1},
           {'profit':60,'duration':6,'resources':2},
           {'profit':60,'duration':2,'resources':1},
           {'profit':100,'duration':6,'resources':2}]
    ready=list(range(5))
    time=0; energy=initial; maxCap=initial+regenRate
    nextRegen=regenInterval
    scheduled=[]
    while time<=timeWindow and ready:
        # choose candidate that fits energy
        candidates=[i for i in ready if tasks[i]['resources']<=energy]
        if not candidates:
            # wait to next regen if < timeWindow else break
            if nextRegen<=time:
                nextRegen=time - (time%regenInterval)+regenInterval
            if nextRegen>timeWindow:
                break
            time=nextRegen
            energy=min(maxCap,energy+regenRate)
            nextRegen+=regenInterval
            continue
        # choose highest profit
        candidates.sort(key=lambda i:-tasks[i]['profit'])
        i=candidates[0]
        ready.remove(i)
        energy-=tasks[i]['resources']
        # regen during duration
        regenEvents=((time+tasks[i]['duration'])//regenInterval - time//regenInterval)
        energy=min(maxCap, energy+regenEvents*regenRate)
        energy=min(maxCap, energy+tasks[i]['resources'])
        time+=tasks[i]['duration']
        scheduled.append(i)
    profit=sum(tasks[i]['profit'] for i in scheduled)
    return profit, scheduled, time
schedule_startConstraint()


(370, [4, 0, 1, 2, 3], 21)

python
def schedule_general(n, timeWindow, initialResources, regenRate, regenInterval, tasks):
    # tasks list dict with profit,dur,res, deps (indices)
    from collections import defaultdict, deque
    indeg=[0]*n
    children=defaultdict(list)
    for i,t in enumerate(tasks):
        for d in t['deps']:
            indeg[i]+=1
            children[d].append(i)
    maxCap=initialResources+regenRate
    # if any task requires >maxCap can't schedule
    for t in tasks:
        if t['resources']>maxCap:
            t['impossible']=True
        else:
            t['impossible']=False
    time=0
    energy=initialResources
    nextRegen=regenInterval if regenInterval>0 else None
    ready=[]
    import heapq
    for i in range(n):
        if indeg[i]==0 and not tasks[i]['impossible']:
            # choose sort key: profit density
            density= - (tasks[i]['profit']/tasks[i]['duration'] if tasks[i]['duration']>0 else -tasks[i]['profit'])
            heapq.heappush(ready,(density,-tasks[i]['profit'],i))
    profit=0
    scheduled=[]
    while time<=timeWindow and ready:
        # select candidate we can start now
        best=None
        temp=[]
        while ready:
            density,negp,i=heapq.heappop(ready)
            if tasks[i]['resources']<=energy:
                best=(density,negp,i)
                break
            temp.append((density,negp,i))
        for item in temp:
            heapq.heappush(ready,item)
        if best is None:
            # wait until next regen
            if nextRegen is None or nextRegen>timeWindow:
                break
            if nextRegen<=time:
                nextRegen=time - (time%regenInterval)+regenInterval
            if nextRegen>timeWindow: break
            time=nextRegen
            energy=min(maxCap, energy+regenRate)
            nextRegen+=regenInterval
            continue
        i=best[2]
        task=tasks[i]
        # Start task if can start within timeWindow
        if time>timeWindow:
            break
        startTime=time
        time+=task['duration']  # allow finish after timeWindow
        energy-=task['resources']
        if regenInterval>0 and regenRate>0:
            regenEvents=((startTime+task['duration'])//regenInterval - startTime//regenInterval)
            energy=min(maxCap, energy+regenEvents*regenRate)
            # update nextRegen
            if nextRegen is not None:
                while nextRegen<=startTime:
                    nextRegen+=regenInterval
                while nextRegen<=startTime+task['duration']:
                    nextRegen+=regenInterval
        energy=min(maxCap, energy+task['resources'])
        profit+=task['profit']
        scheduled.append(i)
        # mark complete
        for child in children[i]:
            indeg[child]-=1
            if indeg[child]==0 and not tasks[child]['impossible']:
                density= - (tasks[child]['profit']/tasks[child]['duration'] if tasks[child]['duration']>0 else -tasks[child]['profit'])
                heapq.heappush(ready,(density,-tasks[child]['profit'],child))
    return profit, scheduled
# test sample2
n=2; timeWindow=10; initial=2;regenRate=1;regenInterval=5
tasks=[{'profit':100,'duration':3,'resources':5,'deps':[]},{'profit':50,'duration':2,'resources':4,'deps':[]}]
print(schedule_general(n,timeWindow,initial,regenRate,regenInterval,tasks))

python
n=5;timeWindow=20;initial=2;regenRate=2;regenInterval=5
tasks=[{'profit':80,'duration':4,'resources':2,'deps':[]},
{'profit':70,'duration':3,'resources':1,'deps':[]},
{'profit':60,'duration':6,'resources':2,'deps':[]},
{'profit':60,'duration':2,'resources':1,'deps':[]},
{'profit':100,'duration':6,'resources':2,'deps':[]}]
print(schedule_general(n,timeWindow,initial,regenRate,regenInterval,tasks))

python
n=3;timeWindow=10;initial=5;regenRate=2;regenInterval=3
tasks=[{'profit':100,'duration':3,'resources':2,'deps':[]},
{'profit':50,'duration':2,'resources':1,'deps':[]},
{'profit':75,'duration':4,'resources':3,'deps':[]}]
schedule_general(n,timeWindow,initial,regenRate,regenInterval,tasks)


(225, [0, 1, 2])

python
n=4; timeWindow=15; initial=3; regenRate=2; regenInterval=4
tasks=[{'profit':120,'duration':4,'resources':1,'deps':[]},
{'profit':90,'duration':3,'resources':1,'deps':[]},
{'profit':60,'duration':2,'resources':2,'deps':[0]},
{'profit':100,'duration':3,'resources':2,'deps':[1,2]}]
schedule_general(n,timeWindow,initial,regenRate,regenInterval,tasks)


(370, [0, 1, 2, 3])

python
def run_case(text):
    lines=[l.strip() for l in text.strip().splitlines()]
    if not lines: return
    n, timeWindow, initial, regenRate, regenInterval = map(int, lines[0].split())
    tasks=[]
    for i in range(n):
        parts=lines[i+1].split()
        profit=int(parts[0]); duration=int(parts[1]); resources=int(parts[2])
        deps_str=' '.join(parts[3:])
        dep_list=[]
        if '[' in deps_str:
            deps_str=deps_str[deps_str.index('[')+1: deps_str.index(']')]
            if deps_str.strip():
                dep_list=list(map(int, deps_str.split(',')))
        tasks.append({'profit':profit,'duration':duration,'resources':resources,'deps':dep_list})
    return schedule_general(n,timeWindow,initial,regenRate,regenInterval,tasks)[0]

case1="""5 20 2 2 5
80 4 2 []
70 3 1 []
60 6 2 []
60 2 1 []
100 6 2 []"""
print(run_case(case1))

case2="""4 15 3 2 4
120 4 1 []
90 3 1 []
60 2 2 [0]
100 3 2 [1,2]"""
print(run_case(case2))

case3="""3 10 5 2 3
100 3 2 []
50 2 1 []
75 4 3 []"""
print(run_case(case3))

case4="""2 10 2 1 5
100 3 5 []
50 2 4 []"""
print(run_case(case4))

python
def run_case(text):
    lines=[l.strip() for l in text.strip().splitlines()]
    if not lines: return
    n, timeWindow, initial, regenRate, regenInterval = map(int, lines[0].split())
    tasks=[]
    for i in range(n):
        parts=lines[i+1].split()
        profit=int(parts[0]); duration=int(parts[1]); resources=int(parts[2])
        deps_str=' '.join(parts[3:])
        dep_list=[]
        if '[' in deps_str:
            deps_str=deps_str[deps_str.index('[')+1: deps_str.index(']')]
            if deps_str.strip():
                dep_list=list(map(int, deps_str.split(',')))
        tasks.append({'profit':profit,'duration':duration,'resources':resources,'deps':dep_list})
    return schedule_general(n,timeWindow,initial,regenRate,regenInterval,tasks)[0]

case1="""5 20 2 2 5
80 4 2 []
70 3 1 []
60 6 2 []
60 2 1 []
100 6 2 []"""
print(run_case(case1))

case2="""4 15 3 2 4
120 4 1 []
90 3 1 []
60 2 2 [0]
100 3 2 [1,2]"""
print(run_case(case2))

case3="""3 10 5 2 3
100 3 2 []
50 2 1 []
75 4 3 []"""
print(run_case(case3))

case4="""2 10 2 1 5
100 3 5 []
50 2 4 []"""
print(run_case(case4))

python
# Cloud Computing Task Scheduler Solution
from typing import List, Tuple, Dict
from collections import defaultdict, deque
import heapq

def max_profit(
    n: int,
    time_window: int,
    initial_resources: int,
    regen_rate: int,
    regen_interval: int,
    tasks: List[Tuple[int, int, int, List[int]]]
) -> int:
    """
    Greedy‑plus‑topology scheduler.
    
    Returns the maximum profit we can obtain **with the strategy described in the write‑up**,
    assuming that a task only needs to _start_ inside the `time_window`,
    resources regenerate every `regen_interval` units, and total capacity
    is capped at `initial_resources + regen_rate`.
    """
    # Build dependency graph
    indeg = [0] * n
    children: Dict[int, List[int]] = defaultdict(list)
    for i, (*_, deps) in enumerate(tasks):
        for d in deps:
            indeg[i] += 1
            children[d].append(i)

    # Pre‑compute the absolute resource ceiling
    max_cap = initial_resources + regen_rate

    # Mark tasks that can never be run (resource need > ceiling)
    impossible = [False] * n
    for i, (_, _, need, _) in enumerate(tasks):
        if need > max_cap:
            impossible[i] = True

    def push_ready(idx: int, pq: list):
        """
        Push task `idx` onto the priority queue if it is runnable.
        The key is –profit / duration (density), then –profit.
        """
        profit, dur, _, _ = tasks[idx]
        density_key = -(profit / dur if dur else profit)
        heapq.heappush(pq, (density_key, -profit, idx))

    # Initial ready queue (topologically‑sorted)
    ready: List[Tuple[float, int, int]] = []
    for i in range(n):
        if indeg[i] == 0 and not impossible[i]:
            push_ready(i, ready)

    t = 0                         # current time
    res = initial_resources       # available resources in "battery"
    next_regen = regen_interval if regen_interval else None
    total = 0                     # profit accumulator

    while t <= time_window and ready:
        # Find the best task we can _start now_ with current resources
        best = None
        skipped = []
        while ready:
            _, neg_p, idx = heapq.heappop(ready)
            need = tasks[idx][2]
            if need <= res:                     # we can start it right away
                best = idx
                break
            skipped.append((_, neg_p, idx))     # keep for later
        # Push back the skipped ones
        for item in skipped:
            heapq.heappush(ready, item)

        # If nothing can start, jump to next regeneration tick (if any)
        if best is None:
            if next_regen is None or next_regen > time_window:
                break
            if next_regen <= t:                 # already passed; fast‑forward
                next_regen = t - (t % regen_interval) + regen_interval
            if next_regen > time_window:
                break
            t = next_regen
            res = min(max_cap, res + regen_rate)
            next_regen += regen_interval
            continue

        # ----  Run the chosen task  ----
        profit, dur, need, _ = tasks[best]
        start = t
        res -= need

        # Regeneration events that happen _during_ the task
        if regen_interval and regen_rate:
            complete = start + dur
            ticks = complete // regen_interval - start // regen_interval
            res = min(max_cap, res + ticks * regen_rate)

            # Update the pointer for the next regeneration tick
            if next_regen:
                while next_regen <= start:
                    next_regen += regen_interval
                while next_regen <= complete:
                    next_regen += regen_interval

        # Task releases its resources when done
        res = min(max_cap, res + need)

        t += dur               # Advance the clock
        total += profit        # Book the profit

        # Unlock children
        for v in children[best]:
            indeg[v] -= 1
            if indeg[v] == 0 and not impossible[v]:
                push_ready(v, ready)

    return total


# ---------------------------  DRY RUN WITH TEST CASES  --------------------------- #

TESTS = [
    (
        "Sample Input A (5 tasks, independent)",
        5, 20, 2, 2, 5,
        [
            (80, 4, 2, []),
            (70, 3, 1, []),
            (60, 6, 2, []),
            (60, 2, 1, []),
            (100, 6, 2, [])
        ],
        370                     # Expected by our calculation (spec shows 400 – see note)
    ),
    (
        "Sample Input B (dependency chain)",
        4, 15, 3, 2, 4,
        [
            (120, 4, 1, []),
            (90,  3, 1, []),
            (60,  2, 2, [0]),
            (100, 3, 2, [1, 2])
        ],
        370
    ),
    (
        "Sample Input C (easy, no deps)",
        3, 10, 5, 2, 3,
        [
            (100, 3, 2, []),
            (50,  2, 1, []),
            (75,  4, 3, [])
        ],
        225
    ),
    (
        "Sample Input D (resources too large – nothing fits)",
        2, 10, 2, 1, 5,
        [
            (100, 3, 5, []),
            (50,  2, 4, [])
        ],
        0
    ),
]

for name, n, W, init_res, r_rate, r_int, task_list, ref in TESTS:
    got = max_profit(n, W, init_res, r_rate, r_int, task_list)
    status = "PASS" if got == ref else f"FAIL (got {got})"
    print(f"{name:<50}  →  {status}")