leetcode No.1235规划兼职工作 动态规划

首先对end进行排序， 将整体数据有序化。
随后， 设f[i]为第i份工作的最大工资
则f[i] = max(f[ i - 1 ], f[ j ] + sal)
j表示在i工作开始之前赚到的最多的工资

typedef struct {
	int start;
	int end;
	int sal;
}Job;


int Max(int a, int b);

int mycomp(const void* a1, const void* a2);
int jobScheduling(int* startTime, int startTimeSize, int* endTime, int endTimeSize, int* profit, int profitSize)
{
	int n = startTimeSize;
	Job* job = (Job*)malloc(sizeof(Job) * n);
	int f[500001] = {0};
	int temp;
	int cursal;
	for (int i = 0; i < n; i++)
	{
		job[i].start = startTime[i];
		job[i].end = endTime[i];
		job[i].sal = profit[i];
	}
	qsort((void *)job, (size_t)n, sizeof(Job), mycomp);

	f[0] = 0;
	int maxsal = 0;
	for (int i = 1; i <= n; i++)
	{
        temp = i - 2;
        while(temp >= 0 && job[temp].end > job[i - 1].start)
            temp--;
        temp += 1;
        cursal = job[i - 1].sal;
		f[i] = Max(f[i - 1],  f[temp] + cursal);
		maxsal = Max(maxsal, f[i]);
	}
	free(job);
	return maxsal;
}


int mycomp(const void* a1, const void* a2)
{
	const Job* b1 = (Job*)a1;
	const Job* b2 = (Job*)a2;
    int ret =  b1->end - b2->end;
    if(ret == 0)
        return b1->sal - b2->sal; 
	return b1->end - b2->end;
}

int Max(int a, int b)
{
	return a > b ? a : b;
}