Interval Independent

Interval Independent.cpp

#include <bits/stdc++.h>

using namespace std;

struct Interval {
	int s, t, w;
};

void solve()
{
	int n;
	scanf("%d", &n);

	Interval inp[n];
	for (int i = 0; i < n; i++)
		scanf("%d %d %d", &inp[i].s, &inp[i].t, &inp[i].w);

	int dp[n];
	sort(inp, inp + n,
	     [](const Interval &a, const Interval &b) -> bool { return a.t < b.t; });
	dp[0] = inp[0].w;
	for (int i = 1; i < n; i++) {
		dp[i] = max(dp[i - 1], inp[i].w);
		int left = -1, right = i;
		while (right - left > 1) {
			int mid = left + (right - left) / 2;
			if (inp[mid].t <= inp[i].s)
				left = mid;
			else
				right = mid;
		}

		// left
		if (left != -1)
			dp[i] = max(dp[i], dp[left] + inp[i].w);
	}

	printf("%d\n", dp[n - 1]);
}

int main()
{
	int ncase;
	scanf("%d", &ncase);

	while (ncase--)
		solve();

	return 0;
}