Session 3

		from itertools import permutations
 
def solve_brute_force(jobs):
    # jobs is a list of tuples: (name, time)
    all_configs = list(permutations(jobs))
    best_time = float("inf")
    best_seq = None
 
    for config in all_configs:
        current_finish_time = 0
        total_system_time = 0
 
        # Calculate completion time for each job in this specific order
        for name, time in config:
            current_finish_time += time
            total_system_time += current_finish_time
 
        print(
            f"Schedule {'-'.join([j[0] for j in config])}: Total Time = {total_system_time}"
        )
 
        # Track the minimum time found
        if total_system_time < best_time:
            best_time = total_system_time
            best_seq = config
 
    print(f"\nOptimal: {'-'.join([j[0] for j in best_seq])} with Time: {best_time}")
 
 
job_list = [("J1", 5), ("J2", 8), ("J3", 12)]
solve_brute_force(job_list)
	

		#include <stdio.h>
#include <string.h>
 
void swap(int *a, int *b) { int temp = *a; *a = *b; *b = temp; }
 
// Function to calculate system time for a given permutation
int calculate_time(int arr[], int n) {
    int current_finish = 0, total = 0;
    for(int i = 0; i < n; i++) {
        current_finish += arr[i];
        total += current_finish;
    }
    return total;
}
 
void find_optimal(int arr[], int start, int n, int *min_time) {
    if (start == n) {
        int current_total = calculate_time(arr, n);
        if (current_total < *min_time) *min_time = current_total;
        return;
    }
    for (int i = start; i < n; i++) {
        swap(&arr[start], &arr[i]); // Generate permutation
        find_optimal(arr, start + 1, n, min_time);
        swap(&arr[start], &arr[i]); // Backtrack
    }
}
 
int main() {
    int times[] = {5, 8, 12};
    int n = 3;
    int min_time = 100000; // Initialize with a large value
 
    find_optimal(times, 0, n, &min_time);
    printf("Optimal Total System Time: %d\n", min_time);
    return 0;
}
	

		fn calculate_total_time(sequence: &Vec<(&str, i32)>) -> i32 {
    let mut current_time = 0;
    let mut total_time = 0;
    for &(_, time) in sequence {
        current_time += time; // Finish time of current job
        total_time += current_time; // Cumulative sum
    }
    total_time
}
 
fn permute(jobs: &mut Vec<(&str, i32)>, start: usize, best: &mut (i32, Vec<String>)) {
    if start == jobs.len() {
        let time = calculate_total_time(jobs);
        if time < best.0 {
            best.0 = time;
            best.1 = jobs.iter().map(|(id, _)| id.to_string()).collect();
        }
        return;
    }
    for i in start..jobs.len() {
        jobs.swap(start, i); // Swap to create new permutation
        permute(jobs, start + 1, best);
        jobs.swap(start, i); // Backtrack
    }
}
 
fn main() {
    let mut jobs = vec![("J1", 5), ("J2", 8), ("J3", 12)];
    let mut best = (i32::MAX, vec![]);
    permute(&mut jobs, 0, &mut best);
    println!("Optimal Schedule: {:?} Total Time: {}", best.1, best.0);
}
	

		def minimize_total_time(jobs):
    # Sort jobs by service time (index 1 of the tuple)
    jobs.sort(key=lambda x: x[1])
 
    current_time = 0
    total_spent = 0
    sequence = []
 
    for job_id, service_time in jobs:
        current_time += service_time  # Time when this specific job finishes
        total_spent += current_time  # Add this finish time to the system total
        sequence.append(str(job_id))
 
    print(f"Optimal Sequence: {' -> '.join(sequence)}")
    print(f"Total Time Spent in System: {total_spent}")
 
 
# Input: (Job ID, Service Time)
job_list = [(1, 5), (2, 10), (3, 7), (4, 8)]
minimize_total_time(job_list)
	

		#include <stdio.h>
#include <stdlib.h>
 
struct Job {
    int id;
    int service_time;
};
 
// Comparator for qsort: sorts in ascending order of service_time
int compare_jobs(const void *a, const void *b) {
    return ((struct Job*)a)->service_time - ((struct Job*)b)->service_time;
}
 
int main() {
    struct Job jobs[] = {{1, 5}, {2, 10}, {3, 7}, {4, 8}};
    int n = 4;
 
    // Sort jobs using Shortest Job First strategy
    qsort(jobs, n, sizeof(struct Job), compare_jobs);
 
    int finish_time = 0;
    int total_system_time = 0;
 
    printf("Optimal Sequence: ");
    for (int i = 0; i < n; i++) {
        finish_time += jobs[i].service_time;   // Completion time of job i
        total_system_time += finish_time;     // Cumulative system wait time
        printf("%d%s", jobs[i].id, (i == n - 1) ? "" : " -> ");
    }
 
    printf("\nTotal Time Spent in System: %d\n", total_system_time);
 
    return 0;
}
	

		#[derive(Debug)]
struct Job {
    id: i32,
    service_time: i32,
}
 
fn main() {
    let mut jobs = vec![
        Job {
            id: 1,
            service_time: 5,
        },
        Job {
            id: 2,
            service_time: 10,
        },
        Job {
            id: 3,
            service_time: 7,
        },
        Job {
            id: 4,
            service_time: 8,
        },
    ];
 
    // Sort jobs by service_time ascending
    jobs.sort_by_key(|j| j.service_time);
 
    let mut finish_time = 0;
    let mut total_system_time = 0;
    let mut sequence = Vec::new();
 
    for job in jobs {
        finish_time += job.service_time; // Cumulative time for this job
        total_system_time += finish_time; // Total time spent across all jobs
        sequence.push(job.id.to_string());
    }
 
    println!("Optimal Sequence: {}", sequence.join(" -> "));
    println!("Total Time Spent in System: {}", total_system_time);
}
	

		def solve_job_sequencing(jobs):
    # 1. Sort jobs by profit in descending order
    # (Job ID, Deadline, Profit)
    jobs.sort(key=lambda x: x[2], reverse=True)
 
    # 2. Find max deadline to size the timeline
    max_d = max(job[1] for job in jobs)
 
    # 3. Initialize slots (0 is ignored, using 1 to max_d)
    slots = [-1] * (max_d + 1)
    total_profit = 0
    count_jobs = 0
 
    for job_id, deadline, profit in jobs:
        # 4. Try to place job in the latest available slot from deadline down to 1
        for j in range(deadline, 0, -1):
            if slots[j] == -1:
                slots[j] = job_id
                total_profit += profit
                count_jobs += 1
                break
 
    # Filter out empty slots for the result
    scheduled_jobs = [slots[i] for i in range(1, max_d + 1) if slots[i] != -1]
    return scheduled_jobs, total_profit
 
 
# Data: (ID, Deadline, Profit)
job_data = [
    (1, 3, 50),
    (2, 4, 20),
    (3, 5, 70),
    (4, 3, 15),
    (5, 2, 10),
    (6, 1, 47),
    (7, 1, 60),
]
sequence, profit = solve_job_sequencing(job_data)
 
print(f"Scheduled Sequence: {sequence}")
print(f"Maximum Profit: {profit}")
	

		#include <stdio.h>
#include <stdlib.h>
 
struct Job {
    int id, deadline, profit;
};
 
// Sort descending based on profit
int compare(const void* a, const void* b) {
    return ((struct Job*)b)->profit - ((struct Job*)a)->profit;
}
 
void schedule_jobs(struct Job jobs[], int n) {
    qsort(jobs, n, sizeof(struct Job), compare);
 
    int max_d = 0;
    for (int i = 0; i < n; i++)
        if (jobs[i].deadline > max_d) max_d = jobs[i].deadline;
 
    int slots[max_d + 1];
    int result[max_d + 1];
    for (int i = 0; i <= max_d; i++) slots[i] = 0; // Initialize as free
 
    int total_profit = 0;
    for (int i = 0; i < n; i++) {
        // Find a slot from its deadline backwards
        for (int j = jobs[i].deadline; j > 0; j--) {
            if (slots[j] == 0) {
                slots[j] = 1; // Mark as occupied
                result[j] = jobs[i].id;
                total_profit += jobs[i].profit;
                break;
            }
        }
    }
 
    printf("Maximum Profit: %d\nScheduled Sequence: ", total_profit);
    for (int i = 1; i <= max_d; i++) {
        if (slots[i]) printf("%d ", result[i]);
    }
    printf("\n");
}
 
int main() {
    struct Job jobs[] = {{1,3,50}, {2,4,20}, {3,5,70}, {4,3,15}, {5,2,10}, {6,1,47}, {7,1,60}};
    int n = sizeof(jobs) / sizeof(jobs[0]);
    schedule_jobs(jobs, n);
    return 0;
}
	

		#[derive(Debug)]
struct Job {
    id: i32,
    deadline: usize,
    profit: i32,
}
 
fn main() {
    let mut jobs = vec![
        Job {
            id: 1,
            deadline: 3,
            profit: 50,
        },
        Job {
            id: 2,
            deadline: 4,
            profit: 20,
        },
        Job {
            id: 3,
            deadline: 5,
            profit: 70,
        },
        Job {
            id: 4,
            deadline: 3,
            profit: 15,
        },
        Job {
            id: 5,
            deadline: 2,
            profit: 10,
        },
        Job {
            id: 6,
            deadline: 1,
            profit: 47,
        },
        Job {
            id: 7,
            deadline: 1,
            profit: 60,
        },
    ];
 
    // Sort by profit descending
    jobs.sort_by(|a, b| b.profit.cmp(&a.profit));
 
    let max_deadline = jobs.iter().map(|j| j.deadline).max().unwrap_or(0);
    let mut slots = vec![0; max_deadline + 1]; // 0 indicates an empty slot
    let mut total_profit = 0;
    let mut sequence = Vec::new();
 
    for job in jobs {
        // Find a free slot for this job (from deadline backwards)
        for t in (1..=job.deadline).rev() {
            if slots[t] == 0 {
                slots[t] = job.id;
                total_profit += job.profit;
                sequence.push(job.id);
                break;
            }
        }
    }
 
    println!("Max Profit: {}", total_profit);
    println!("Scheduled Jobs (in order of assignment): {:?}", sequence);
}