Greedy - Exchange Argument

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
struct Job {
5
    int id;                // original index
6
    long long p;           // processing time
7
};
8
9
int main() {
10
    ios::sync_with_stdio(false);
11
    cin.tie(nullptr);
12
13
    // Example jobs (processing times)
14
    vector<Job> jobs = {{0, 3}, {1, 1}, {2, 2}, {3, 7}};
15
16
    // Greedy: Shortest Processing Time first (SPT)
17
    sort(jobs.begin(), jobs.end(), [](const Job& a, const Job& b){
18
        if (a.p != b.p) return a.p < b.p; // increasing p
19
        return a.id < b.id;               // stable tie-break by id
20
    });
21
22
    long long time = 0;       // current time (prefix sum of p)
23
    long long sumC = 0;       // sum of completion times
24
    vector<int> order; order.reserve(jobs.size());
25
26
    for (const auto& j : jobs) {
27
        time += j.p;          // job completes at current time + p
28
        sumC += time;         // add completion time
29
        order.push_back(j.id);
30
    }
31
32
    cout << "Order (by original id): ";
33
    for (int i = 0; i < (int)order.size(); ++i) {
34
        if (i) cout << ' ';
35
        cout << order[i];
36
    }
37
    cout << "\n";
38
    cout << "Sum of completion times = " << sumC << "\n";
39
40
    // Note: Exchange argument justification (pairwise):
41
    // If two adjacent jobs have p_i > p_j, swapping them decreases total sum by (p_i - p_j).
42
    // Repeating swaps (like bubble sort inversions) yields SPT which is optimal.
43
44
    return 0;
45
}
46

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
struct Job {
5
    int id;
6
    long long p; // processing time
7
    long long w; // weight (importance)
8
};
9
10
// Safe comparator for p_i / w_i without floating point: compare a.p * b.w vs b.p * a.w
11
// Use 128-bit to avoid overflow when multiplying two 64-bit numbers.
12
bool smithCmp(const Job& a, const Job& b) {
13
    __int128 lhs = (__int128)a.p * (__int128)b.w;
14
    __int128 rhs = (__int128)b.p * (__int128)a.w;
15
    if (lhs != rhs) return lhs < rhs; // increasing p/w
16
    return a.id < b.id;               // tie-breaker for stability
17
}
18
19
int main() {
20
    ios::sync_with_stdio(false);
21
    cin.tie(nullptr);
22
23
    // Example jobs (p, w)
24
    vector<Job> jobs = {
25
        {0, 6, 3},  // ratio 2.0
26
        {1, 3, 1},  // ratio 3.0
27
        {2, 5, 5},  // ratio 1.0
28
        {3, 4, 2}   // ratio 2.0
29
    };
30
31
    sort(jobs.begin(), jobs.end(), smithCmp);
32
33
    long long time = 0;
34
    long long weightedSum = 0;
35
    vector<int> order; order.reserve(jobs.size());
36
37
    for (const auto& j : jobs) {
38
        time += j.p;
39
        weightedSum += j.w * time; // accumulate w_i * C_i
40
        order.push_back(j.id);
41
    }
42
43
    cout << "Order (by original id): ";
44
    for (int i = 0; i < (int)order.size(); ++i) {
45
        if (i) cout << ' ';
46
        cout << order[i];
47
    }
48
    cout << "\nWeighted sum of completion times = " << weightedSum << "\n";
49
50
    // Exchange argument: For two jobs i, j, prefer i before j iff w_j * p_i <= w_i * p_j,
51
    // equivalently p_i / w_i <= p_j / w_j. Swapping any violating adjacent pair reduces \sum w_k C_k.
52
53
    return 0;
54
}
55

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
struct Interval {
5
    int id;
6
    int s, f; // start and finish times
7
};
8
9
int main() {
10
    ios::sync_with_stdio(false);
11
    cin.tie(nullptr);
12
13
    vector<Interval> a = {
14
        {0, 1, 3}, {1, 2, 5}, {2, 4, 7}, {3, 1, 2}, {4, 6, 9}, {5, 8, 10}
15
    };
16
17
    sort(a.begin(), a.end(), [](const Interval& x, const Interval& y){
18
        if (x.f != y.f) return x.f < y.f; // earliest finishing time first
19
        return x.s < y.s;                 // tie-break by start time
20
    });
21
22
    vector<int> chosen;
23
    int lastFinish = INT_MIN; // or -infinity
24
    for (const auto& it : a) {
25
        if (it.s >= lastFinish) {
26
            chosen.push_back(it.id);
27
            lastFinish = it.f;
28
        }
29
    }
30
31
    cout << "Chosen interval ids: ";
32
    for (int i = 0; i < (int)chosen.size(); ++i) {
33
        if (i) cout << ' ';
34
        cout << chosen[i];
35
    }
36
    cout << "\n";
37
38
    // Exchange-style structural proof sketch:
39
    // Among all optimal solutions, take one with the earliest finishing first interval.
40
    // If its first interval finishes later than the greedy's first choice, exchange them: feasibility holds and size is preserved.
41
    // Repeating aligns the optimal solution with the greedy one.
42
43
    return 0;
44
}
45

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
struct Job {
5
    int id;
6
    long long p; // processing time
7
    long long d; // due date
8
};
9
10
int main() {
11
    ios::sync_with_stdio(false);
12
    cin.tie(nullptr);
13
14
    vector<Job> jobs = {
15
        {0, 3, 4}, {1, 2, 5}, {2, 7, 20}, {3, 4, 8}
16
    };
17
18
    sort(jobs.begin(), jobs.end(), [](const Job& a, const Job& b){
19
        if (a.d != b.d) return a.d < b.d; // earliest due date first
20
        return a.id < b.id;
21
    });
22
23
    long long t = 0;
24
    long long Lmax = LLONG_MIN;
25
    vector<int> order; order.reserve(jobs.size());
26
27
    for (const auto& j : jobs) {
28
        t += j.p;                    // completion time C_j
29
        long long L = t - j.d;       // lateness
30
        Lmax = max(Lmax, L);
31
        order.push_back(j.id);
32
    }
33
34
    cout << "Order (by original id): ";
35
    for (int i = 0; i < (int)order.size(); ++i) {
36
        if (i) cout << ' ';
37
        cout << order[i];
38
    }
39
    cout << "\nMax lateness Lmax = " << Lmax << "\n";
40
41
    // Exchange argument: If two adjacent jobs are out of EDD order (d_i > d_j), swapping them cannot increase L_max.
42
    // Therefore, repeatedly fixing inversions yields EDD, which minimizes maximum lateness.
43
44
    return 0;
45
}
46