Lap_Lich.cpp

// Lap_Lich.cpp
#include <bits/stdc++.h>

using namespace std;

struct Lich {
	float s;
	float f;
};

void Swap(Lich &a, Lich &b) {
	Lich tmp = a;
	a = b;
	b = tmp;
}

void Quick_Sort(Lich a[], int left, int right, bool asc = true) {
	float pivot = a[(left + right) / 2].s;
	int i = left;
	int j = right;
	while (i < j) {
		while (a[i].s < pivot == asc) {
			i++;
		}
		while (a[j].s > pivot == asc) {
			j--;
		}
		if (i <= j) {
			Swap(a[i], a[j]);
			i++;
			j--;
		}
	}
	if (i < right) {
		Quick_Sort(a, i, right, asc);
	}
	if (left < j) {
		Quick_Sort(a, left, j, asc);
	}
}

void Interval_Scheduling(Lich sc[], int n, int *schedule) {
	Quick_Sort(sc, 0, 4, true);
	float last_finish = 0;
	for (int i = 0; i < n; i++) {
		if (sc[i].s >= last_finish) {
			schedule[i] = 1;
			last_finish = sc[i].f;
		}
	}
	for (int i = 0; i < n; i++) {
		cout << schedule[i] << " ";
	}
}

int main() {
	int n = 5;
	Lich sc[] = {
		{8, 8.5},
		{9, 11},
		{10, 11.5},
		{11, 12.5},
		{12, 13}
	};
	int *schedule = (int*)calloc(n, sizeof(int));
	cout << "Input:" << endl;
	cout << n << endl;
	for (int i = 0; i < n; i++) cout << sc[i].s << " ";
	cout << endl;
	for (int i = 0; i < n; i++) cout << sc[i].f << " ";
	cout << endl;
	cout << "Output:" << endl;
	Interval_Scheduling(sc, n, schedule);
	return 0;
}