समस्या
प्रत्येक परियोजना को [start_day, end_day, reward] के रूप में दर्शाया गया है। यह परियोजना start_day से लेकर end_day तक के सभी दिनों को घेरती है, दोनों छोर शामिल हैं। आप किसी भी दिन केवल एक परियोजना में भाग ले सकते हैं। अधिकतम कुल पुरस्कार के लिए परियोजनाओं का एक उपसमुच्चय चुनें। यदि कोई परियोजना किसी अन्य परियोजना के end_day पर शुरू होती है, तो वे एक-दूसरे के साथ संघर्ष करती हैं।
project_rewards(projects) को लागू करें।
इनपुट
projects: तीन पूर्णांकों की पंक्तियाँ: प्रारंभ दिनांक, समाप्ति दिनांक, और पुरस्कार।
आउटपुट
अधिकतम कुल पुरस्कार लौटाएँ; चुनी गई परियोजनाएँ लौटाना आवश्यक नहीं है।
सीमाएँ
1 ≤ projects ≤ 200,000। 1 ≤ start_day ≤ end_day ≤ 1,000,000,000। पुरस्कार सकारात्मक पूर्णांक हैं, अधिकतम 1,000,000,000।
उदाहरण
इनपुट:
projects = [
[1, 2, 4],
[3, 4, 5],
[2, 3, 10]
]
अपेक्षित आउटपुट:
expected = 10इनपुट:
std::vector<std::vector<long long>> projects = {
{1, 2, 4},
{3, 4, 5},
{2, 3, 10}
};
अपेक्षित आउटपुट:
long long expected = 10;इनपुट:
long[][] projects = new long[][] {
new long[] {1, 2, 4},
new long[] {3, 4, 5},
new long[] {2, 3, 10}
};
अपेक्षित आउटपुट:
long expected = 10;व्याख्या
पहली दो परियोजनाएँ मिलकर 9 का पुरस्कार देती हैं। अंतिम परियोजना का पुरस्कार 10 है, लेकिन वह दोनों के साथ संघर्ष करती है, इसलिए केवल उसे चुनें।
इनपुट:
projects = [
[1, 2, 4],
[2, 3, 5]
]
अपेक्षित आउटपुट:
expected = 5इनपुट:
std::vector<std::vector<long long>> projects = {
{1, 2, 4},
{2, 3, 5}
};
अपेक्षित आउटपुट:
long long expected = 5;इनपुट:
long[][] projects = new long[][] {
new long[] {1, 2, 4},
new long[] {2, 3, 5}
};
अपेक्षित आउटपुट:
long expected = 5;व्याख्या
दोनों परियोजनाएँ दिनांक 2 को आती हैं। केवल दूसरी परियोजना चुनें, जिसका पुरस्कार 5 है।
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
यह overlapping time ranges वाला weighted interval scheduling problem है.
संकेत 2
Projects को end day के अनुसार sort करो और हर project को latest compatible earlier project से combine करो.
संकेत 3
Conflicts को ठीक से समझो: end day पर शुरू होने वाला दूसरा project भी overlap करता है.
अपेक्षित जटिलता
समय O(n log n), अतिरिक्त स्थान O(n)
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।