Maximum Number of Weeks for Which You Can Work

Maximum Number of Weeks for Which You Can Work - Problem

Array Greedy Medium

There are n projects numbered from 0 to n - 1. You are given an integer array milestones where each milestones[i] denotes the number of milestones the ith project has.

You can work on the projects following these two rules:

Every week, you will finish exactly one milestone of one project. You must work every week.
You cannot work on two milestones from the same project for two consecutive weeks.

Once all the milestones of all the projects are finished, or if the only milestones that you can work on will cause you to violate the above rules, you will stop working. Note that you may not be able to finish every project's milestones due to these constraints.

Return the maximum number of weeks you would be able to work on the projects without violating the rules mentioned above.

Input & Output

Example 1 — Basic Case

$ Input: milestones = [1,2,3]

› Output: 6

💡 Note: We can work on all milestones: Week 1-Project 2, Week 2-Project 1, Week 3-Project 2, Week 4-Project 0, Week 5-Project 2, Week 6-Project 1. Total: 6 weeks.

Example 2 — Constraint Limiting

$ Input: milestones = [5,2,1]

› Output: 7

💡 Note: Project 0 has 5 milestones, others have 3 total. We can work: P0-P1-P0-P2-P0-P1-P0, then stop (can't work on P0 again). Total: 7 weeks.

Example 3 — Equal Projects

$ Input: milestones = [5,5,5]

› Output: 15

💡 Note: All projects equal, can perfectly interleave: P0-P1-P2-P0-P1-P2... until all done. Total: 15 weeks.

Constraints

n == milestones.length
1 ≤ n ≤ 10⁵
1 ≤ milestones[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Array of project milestones: [1,2,3]

Constraint

Cannot work same project two consecutive weeks

Schedule

Find optimal interleaving pattern

Output

Maximum weeks possible: 6

Key Takeaway

🎯 Key Insight: Maximum weeks depends on whether the largest project can be interleaved with all others

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is that we can work maximum weeks when the largest project can be perfectly interleaved with all other projects. If the largest project has more milestones than all others combined plus one, we're constrained by the interleaving rule. Best approach uses mathematical greedy analysis in O(n) time.

Common Approaches

Approach	Time	Space	Notes
✓ Simulation with Priority Queue	O(n log n)	O(n)	Simulate the work process by always choosing the project with most remaining milestones
Mathematical Greedy Solution	O(n)	O(1)	Use mathematical insight to determine if all milestones can be completed

Simulation with Priority Queue — Algorithm Steps

Build max heap from milestones
Each week, work on project with most milestones
Skip that project next week
Continue until no valid projects remain

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Heap

Create max heap from project milestones

Work Weekly

Always choose project with most remaining work

Count Weeks

Continue until no valid projects remain

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int *data;
    int size;
    int capacity;
} MaxHeap;

MaxHeap* createHeap(int capacity) {
    MaxHeap* heap = malloc(sizeof(MaxHeap));
    heap->data = malloc(capacity * sizeof(int));
    heap->size = 0;
    heap->capacity = capacity;
    return heap;
}

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

void heapifyUp(MaxHeap* heap, int idx) {
    while (idx > 0) {
        int parent = (idx - 1) / 2;
        if (heap->data[parent] >= heap->data[idx]) break;
        swap(&heap->data[parent], &heap->data[idx]);
        idx = parent;
    }
}

void heapifyDown(MaxHeap* heap, int idx) {
    while (2 * idx + 1 < heap->size) {
        int maxChild = 2 * idx + 1;
        if (2 * idx + 2 < heap->size && heap->data[2 * idx + 2] > heap->data[maxChild]) {
            maxChild = 2 * idx + 2;
        }
        if (heap->data[idx] >= heap->data[maxChild]) break;
        swap(&heap->data[idx], &heap->data[maxChild]);
        idx = maxChild;
    }
}

void push(MaxHeap* heap, int val) {
    heap->data[heap->size] = val;
    heapifyUp(heap, heap->size);
    heap->size++;
}

int pop(MaxHeap* heap) {
    int top = heap->data[0];
    heap->data[0] = heap->data[heap->size - 1];
    heap->size--;
    if (heap->size > 0) heapifyDown(heap, 0);
    return top;
}

long long solution(int* milestones, int milestonesSize) {
    MaxHeap* heap = createHeap(milestonesSize);
    for (int i = 0; i < milestonesSize; i++) {
        if (milestones[i] > 0) {
            push(heap, milestones[i]);
        }
    }
    
    long long weeks = 0;
    int prevProjectMilestones = 0;
    
    while (heap->size > 0) {
        int currentMilestones = pop(heap);
        weeks++;
        int remaining = currentMilestones - 1;
        
        if (prevProjectMilestones > 0) {
            push(heap, prevProjectMilestones);
        }
        
        if (remaining > 0 && heap->size == 0) {
            break;
        }
        
        prevProjectMilestones = remaining;
    }
    
    free(heap->data);
    free(heap);
    return weeks;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int milestones[1000];
    int size = 0;
    
    char *token = strtok(line, "[,]");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != ' ' && token[0] != '\n') {
            milestones[size++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    printf("%lld\n", solution(milestones, size));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Each of the potentially thousands of weeks requires heap operations taking O(log n)

⚡ Linearithmic

Space Complexity

O(n)

Priority queue stores all n projects

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Simulation with Priority Queue — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler