زمانبندی پردازه‌های وزن‌دار

فرض کنید شما تعدادی سفارش کار دارید، اما وقت این را ندارید که تمام آن‌ها را انجام دهید. هر کدام از این کار‌ها زمان شروع ثابتی دارند و مدت زمان ثابتی طول می‌کشند، برای انجام هر کار نیز مقداری پول می‌گیرید و این مقادیر لزوما با یکدیگر برابر نیستند. در کل هدف شما این است که بیشترین پول ممکن را بگیرید و برای این کار، باید انتخاب کنید که کدام کارها را می‌خواهید انجام دهید و کدام را نمی‌خواهید.
شما در هر لحظه فقط می‌توانید یک کار را انجام دهید، پس مجموعه‌ی انتخاب‌شده، نباید اشتراک زمانی داشته باشند. برای راحتی فرض کنید می‌توانید بلافاصله بعد از این که یک کار تمام شد، کار بعدی را شروع کنید. یعنی اگر یک کار از ثانیه‌ی ۱۰ تا ۲۰ طول بکشد، شما می‌توانید کار دیگری که در ثانیه‌ی ۲۰ شروع می‌شود را نیز بعد از کار اول انجام دهید.

اولین چیزی که خوب است به آن دقت کنید این است که برای ما فقط زمان‌هایی که در آن‌ها کاری شروع یا تمام می‌شود، مهم است. پس هرچقدر که بازه‌های زمانی، بزرگ باشند، اگر تعداد کار‌ها را $n$ بگیریم آن‌ها را می‌توان به حداکثر $2n$ نقطه‌ی زمانی تبدیل و از این به بعد فقط با این نقطه‌ها کار کرد. کار دیگری که به نظر خوب می‌آید، مرتب کردن کارها به ترتیب زمانی است و مرتب سازی به ترتیب شروع کارها همانطور که بعدا می‌بینیم، به نظر روش خوبی است.
بیایید سعی کنیم سوال را به روش برنامه‌ریزی پویا حل کنیم. یک تعریف که شاید بد نباشد، این است که $d_t$ برابر بیشترین مقدار سودی باشد که می‌توانیم به دست بیاوریم، اگر آخرین کاری که انجام دادیم، در لحظه‌ی $t$ تمام شود. در این صورت، اگر تمامی مقدار‌های $d_i$ به ازای $ i < t $ را داشته باشیم، می‌توانیم مقدار $d_t$ را از روی تمامی کار‌هایی که در لحظه‌ی $t$ تمام می‌شوندَ، به صورت زیر محاسبه کنیم:
($W$ را مجموعه‌ی تمام کار‌ها در نظر بگیرید و برای هر کار $w \in W$ ، مقدار‌های $w.s$ و $w.e$ و $w.c$ را به ترتیب، زمان شروع، پایان و مزد آن کار در نظر بگیرید.) $$ d_t = \max_{\substack{ \forall \: w \in W, \; w.e \, = \, t \\ \forall \: t' \leq w.s }}\big( d_{t'} + w.c \big) $$ البته در هنگام کد زدن بهتر است، به جای اینکه به ازای هر زمان $t$ مقدار $d_t$ را از روی کار‌هایی که در این زمان تمام می‌شوند حساب کنیم، به ازای هر کار، زمانی که تمام می‌شود را از روی خودش به روز رسانی کنیم. این کد را می‌توانید در زیر ببینید:
(فرض کنید کارها به ترتیب شروع مرتب شده‌اند. پس وقتی به کاری می‌رسیم، تمام مقادیر $d$ برای زمان‌های قبل از شروعش، محاسبه شده اند و قرار نیست تغییر کنند. همچنین، $T$ را تعداد نقطه‌های زمانی مختلف بگیرید که حداکثر $2n$ است)

for i from 0 to T
	d[i] = inf
d[0] = 0

for i from 0 to n
	for tprime from 0 to w[i].s
		d[w[i].e] = min( d[w[i].e] , d[tprime] + w.c )

حافظه‌ی مورد نیاز از $O(n)$ است و چون تعداد زمان‌های محتلف که در بالا استفاده می‌کنیم، $2n$ است همانطور که از کد بالا معلوم است، پیچیدگی زمانی از $O(n^2)$ است. البته اگر تعداد زمان‌های مختلف کمتر از این باشد و آن را با $T$ نشان دهیم، پیچیدگی زمانی از $O(n \times T)$ نیز هست.

اگر تعریف‌مان را کمی عوض کنیم، می‌توانیم الگوریتم بالا را سریع‌تر هم بکنیم. فرض کنید $new \_ d_t$ را اینگونه تعریف کنیم که مقدار $new \_ d_t$ برابر بیشترین مقدار سودی باشد که می‌توانیم تا لحظه‌ی $t$ کسب کنیم. طبق این تعریف، می‌توانیم مقدار‌های جدید را از روی مقدارهای قبلی به این صورت حساب کنیم: $$ new \_ d_t = \min_{ t' \leq t } \big( d_{t'} \big) $$ که یعنی: $$ new \_ d_t = \min \big( new \_ d_{t-1} , d_t \big) $$ و با این تعریف جدید، فرمول محاسبه به صورت زیر در می‌آید: $$ d_t = \max_{\forall \: w \in W, \; w.e \, = \, t }\big( new \_ d_{w.s} + w.c \big) $$ و جواب مسئله نیز، $new \_ d_T$ است.
همچنین، می‌توانیم این مقدار‌های جدید را همانطور که داریم از زمان اولی به آخری می‌رویم، قبل از این که به آن‌ها نیاز پیدا کنیم، از روی مقادیر قبلی محاسبه کنیم. کد آن را می‌توانید در زیر ببینید:

for i from 0 to T
	d[i] = inf
d[0] = 0
new_d[0] = 0

last_not_updated = 1

for i from 0 to n

	while last_not_updated < w[i].s
		new_d[last_not_updated] = min( new_d[last_not_updated - 1] + d[last_not_updated] )
		last_not_updated += 1

	d[w[i].e] = min( d[w[i].e] , new_d[w[i].s] + w.c )

while last_not_updated <= T
	new_d[last_not_updated] = min( new_d[last_not_updated - 1] + d[last_not_updated] )
	last_not_updated += 1

اگر دقت کنید، حلقه‌ی $while$ در کد بالا (منظور هم کد داخلی و هم کد بیرونی است)، شاید در بعضی مواقع زیاد طول بکشد اما در مجموع، فقط $T$ بار اجرا می‌شود. پس پیچیدگی زمانی کد بالا از $O(n)$ است، اما دقت کنید که در مرحله‌ی آماده‌سازی الگوریتم مرتب‌سازی را اجرا کردیم که از $O(n.lgn)$ است. پس کل الگوریتم از $O(n.lgn)$ است. حافظه هم مثل قبل از $O(n)$ است.