Schedule jobs on a fixed number of machines to minimize total completion time.

# Job Scheduling - Greedy Approach # Description: Schedules jobs on a fixed number of machines to minimize total completion time by assigning each job to the machine with the least current load. # Job Scheduling - Greedy Load Balancing Algorithm def schedule_jobs(jobs, num_machines): """ Distribute jobs across machines to minimize total completion time. The algorithm uses a greedy approach to balance workload: 1. Sort jobs in descending order to prioritize larger jobs 2. Assign each job to the least loaded machine Args: jobs (list of int): Duration of each job to be scheduled num_machines (int): Number of available machines to distribute jobs Returns: list of int: Total load on each machine after job assignment Time Complexity: O(n log n + n * m) Space Complexity: O(m), where n is number of jobs, m is number of machines Example: # Distribute 5 jobs across 3 machines >>> schedule_jobs([10, 15, 20, 25, 30], 3) [40, 40, 40] """ # Validate input if not jobs or num_machines

Mar 28, 2025 - 04:49

Schedule jobs on a fixed number of machines to minimize total completion time.

# Job Scheduling - Greedy Approach
# Description: Schedules jobs on a fixed number of machines to minimize total completion time by assigning each job to the machine with the least current load.

# Job Scheduling - Greedy Load Balancing Algorithm
def schedule_jobs(jobs, num_machines):
    """
    Distribute jobs across machines to minimize total completion time.

    The algorithm uses a greedy approach to balance workload:
    1. Sort jobs in descending order to prioritize larger jobs
    2. Assign each job to the least loaded machine

    Args:
        jobs (list of int): Duration of each job to be scheduled
        num_machines (int): Number of available machines to distribute jobs

    Returns:
        list of int: Total load on each machine after job assignment

    Time Complexity: O(n log n + n * m)
    Space Complexity: O(m), where n is number of jobs, m is number of machines

    Example:
        # Distribute 5 jobs across 3 machines
        >>> schedule_jobs([10, 15, 20, 25, 30], 3)
        [40, 40, 40]
    """
    # Validate input
    if not jobs or num_machines <= 0:
        return []

    # Sort jobs in descending order to optimize load balancing
    sorted_jobs = sorted(jobs, reverse=True)

    # Initialize machine loads
    machine_loads = [0] * num_machines

    # Assign each job to the least loaded machine
    for job in sorted_jobs:
        # Find the machine with minimum current load
        min_load_index = machine_loads.index(min(machine_loads))

        # Add job to the least loaded machine
        machine_loads[min_load_index] += job

    return machine_loads

# Demonstration of job scheduling
def demonstrate_job_scheduling():
    """
    Demonstrate the job scheduling algorithm with sample inputs.
    """
    # Test case 1: Even distribution
    jobs1 = [10, 15, 20, 25, 30]
    machines1 = 3
    print(f"Jobs {jobs1} on {machines1} machines:")
    print(schedule_jobs(jobs1, machines1))

    # Test case 2: Uneven job distribution
    jobs2 = [5, 8, 12, 13, 16, 20, 25, 30]
    machines2 = 4
    print(f"\nJobs {jobs2} on {machines2} machines:")
    print(schedule_jobs(jobs2, machines2))