Tous les défis
Difficile 1 résolu 100.0 % de réussite

Maximum Project Rewards

Choose nonoverlapping projects to earn the largest total reward.

Ce que vous allez apprendre

  • Sort intervals by end time
  • Find the last compatible project with binary search
  • Choose between taking and skipping a project

Problème

Afficher la traduction

Each project is [start_day, end_day, reward]. It occupies every day from start_day through end_day, including both endpoints. You can participate in only one project on a day. Choose a subset with the largest total reward. A project starting on another project’s end day conflicts with it.

Implement project_rewards(projects).

Input

projects: Rows of three integers: start day, end day, and reward.

Output

Return the maximum total reward; the chosen projects need not be returned.

Contraintes

1 ≤ projects ≤ 200,000. 1 ≤ start_day ≤ end_day ≤ 1,000,000,000. Rewards are positive integers at most 1,000,000,000.

Exemples

Exemple 1
Entrée :
projects = [
    [1, 2, 4],
    [3, 4, 5],
    [2, 3, 10]
]

Sortie attendue :
expected = 10
Entrée :
std::vector<std::vector<long long>> projects = {
    {1, 2, 4},
    {3, 4, 5},
    {2, 3, 10}
};

Sortie attendue :
long long expected = 10;
Entrée :
long[][] projects = new long[][] {
    new long[] {1, 2, 4},
    new long[] {3, 4, 5},
    new long[] {2, 3, 10}
};

Sortie attendue :
long expected = 10;

Explication

The first two projects earn 9 together. The last earns 10 and conflicts with both, so choose it alone.

Exemple 2
Entrée :
projects = [
    [1, 2, 4],
    [2, 3, 5]
]

Sortie attendue :
expected = 5
Entrée :
std::vector<std::vector<long long>> projects = {
    {1, 2, 4},
    {2, 3, 5}
};

Sortie attendue :
long long expected = 5;
Entrée :
long[][] projects = new long[][] {
    new long[] {1, 2, 4},
    new long[] {2, 3, 5}
};

Sortie attendue :
long expected = 5;

Explication

Both occupy day 2. Choose only the second, with reward 5.

Comment l'aborder

Essayez d'abord seul, puis ouvrez les indices un par un.

Indice 1

This is a weighted interval scheduling problem with overlapping time ranges.

Indice 2

Sort projects by end day and combine each project with the latest compatible earlier one.

Indice 3

Be precise about conflicts: another project starting on an end day still overlaps.

Complexité attendue

O(n log n) time, O(n) extra space

Références

Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.

La meilleure solution validée de chaque codeur. Les plus rapides, les plus légères et les mieux notées passent devant.

# Codeur Langage Temps Mémoire Note de l'IA Solution
1 ННикита Python 800 ms - 5/5 Voir le code

Apprenez des autres

Solutions de la communauté

Attention spoiler : 1 solution complète ci-dessous Essayez d'abord de le résoudre vous-même. Vous pouvez toujours jeter un œil au code des autres développeurs et aux avis IA. Connectez-vous et résolvez le défi pour rejoindre la discussion.