Click here to Skip to main content
15,867,308 members
Please Sign up or sign in to vote.
1.00/5 (4 votes)
See more:
#include <bits/stdc++.h>
using namespace std;
class job
{
public:
    int st, ed, cost;
};
int getTime(string s)
{
    int hr = (s[0] – ‘0’) * 10 + (s[1] – ‘0’);
    int min = (s[2] – ‘0’) * 10 + (s[3] – ‘0’);
 
    return hr * 60 + min;
}
bool compare(job A, job B)
{
    return A.ed < B.ed;
}
int searchJob(job arr[], int st, int ed, int key)
{
    int ans = –1;
    while (st <= ed)
    {
        int mid = (st + ed) / 2;
        if (arr[mid].ed <= key)
        {
            ans = mid;
            st = mid + 1;
        }
        else
        {
            ed = mid – 1;
        }
    }
    return ans;
}
pair<int, int> solve(job arr[], int n)
{
    int dp[n] = {0};
    int numOfJobs[n] = {0};
 
    dp[0] = arr[0].cost;
    numOfJobs[0] = 1;
 
    for (int i = 1; i < n; i++)
    {
        int cur = arr[i].cost;
        int num = 1;
        int idx = searchJob(arr, 0, i – 1, arr[i].st);
 
        if (idx != cur)
        {
            cur += dp[idx];
            num += numOfJobs[idx];
        }
        if (cur > dp[i – 1])
        {
            dp[i] = cur;
            numOfJobs[i] = num;
        }
        else
        {
            dp[i] = dp[i – 1];
            numOfJobs[i] = numOfJobs[i – 1];
        }
    }
    return {numOfJobs[n – 1], dp[n – 1]};
}
int main()
{
    int n;
    cin >> n;
 
    job arr[n];
    int cost;
    string st, ed;
    int total = 0;
 
    for (int i = 0; i < n; i++)
    {
        cin >> st >> ed >> cost;
        arr[i].st = getTime(st);
        arr[i].ed = getTime(ed);
        arr[i].cost = cost;
        total += cost;
    }
    sort(arr, arr + n, compare);
 
    pair<int, int> res = solve(arr, n);
 
    cout << n – res.first << endl;
    cout << total – res.second << endl;
 
    return 0;
}


What I have tried:

C++
#include <stdio..h>
int getTime(string s)
{
    int hr = (s[0] – ‘0’) * 10 + (s[1] – ‘0’);
    int min = (s[2] – ‘0’) * 10 + (s[3] – ‘0’);
 
    return hr * 60 + min;
}
int searchJob(job arr[], int st, int ed, int key)
{
    int ans = –1;
    while (st <= ed)
    {
        int mid = (st + ed) / 2;
        if (arr[mid].ed <= key)
        {
            ans = mid;
            st = mid + 1;
        }
        else
        {
            ed = mid – 1;
        }
    }
    return ans;
}
pair<int, int=""> solve(job arr[], int n)
{
    int dp[n] = {0};
    int numOfJobs[n] = {0};
 
    dp[0] = arr[0].cost;
    numOfJobs[0] = 1;
 
    for (int i = 1; i < n; i++)
    {
        int cur = arr[i].cost;
        int num = 1;
        int idx = searchJob(arr, 0, i – 1, arr[i].st);
 
        if (idx != cur)
        {
            cur += dp[idx];
            num += numOfJobs[idx];
        }
        if (cur > dp[i – 1])
        {
            dp[i] = cur;
            numOfJobs[i] = num;
        }
        else
        {
            dp[i] = dp[i – 1];
            numOfJobs[i] = numOfJobs[i – 1];
        }
    }
    return {numOfJobs[n – 1], dp[n – 1]};
}
int main()
{
    int n;
    cin >> n;
 
    job arr[n];
    int cost;
    string st, ed;
    int total = 0;
 
    for (int i = 0; i < n; i++)
    {
        cin >> st >> ed >> cost;
        arr[i].st = getTime(st);
        arr[i].ed = getTime(ed);
        arr[i].cost = cost;
        total += cost;
    }
    sort(arr, arr + n, compare);
 
    pair<int, int=""> res = solve(arr, n);
 
    cout << n – res.first << endl;
    cout << total – res.second << endl;
 
    return 0;
}
Posted
Updated 26-Feb-23 8:51am
v2
Comments
0x01AA 26-Feb-23 13:35pm    
And, where is the problem exactly?

This is not a code translation service: even if it was, converting C++ to C will not give you "good" C code.
C is an old language from which C++ was evolved: it doesn't contain much of what C++ does at all - classes, vectors, tuples for example are all C++ only.
And while it is possible to recode cin and cout to their more primitive C equivalents, replacing the other C++ specific features would produce horrible complicated code to do a simple task.

Instead, throw that away, and write your own C code to do the job - you'll learn things and produce better code.
 
Share this answer
 
Comments
Nelek 26-Feb-23 14:20pm    
:thumbsup:
There are some wrong characters here that don't make sense as code.
Strings are encoded as a char array.
C
//#include <stdio..h>
#include <stdio.h>

//int getTime(string s)
int getTime(char* s)
{
	if (strlen(s) < 4)
		return 0;
	// int hr = (s[0] – ‘0’) * 10 + (s[1] – ‘0’);
	int hr = (s[0] - '0') * 10 + (s[1] - '0');
	// int min = (s[2] – ‘0’) * 10 + (s[3] – ‘0’);
	int min = (s[2] - '0') * 10 + (s[3] - '0');

	return hr * 60 + min;
}
 
Share this answer
 

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900