BYJU’s Coding Questions with Answers

#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;
}

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
class Job {
    public Integer st;
    public Integer ed;
    public Integer cost;

    public Job() {
        super();
    }

    public Job(Integer st, Integer ed, Integer cost) {
        super();
        this.st = st;
        this.ed = ed;
        this.cost = cost;
    }
}
class Pair {
    public Integer first;
    public Integer second;
    public Pair() {
        super();
    }
    public Pair(Integer first, Integer second) {
        super();
        this.first = first;
        this.second = second;
    }
}
class SortingJobs implements Comparator < Job > {

    @Override
    public int compare(Job o1, Job o2) {
        if (o1.ed < o2.ed) {
            return 1;
        } else {
            return 0;
        }
    }
}
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Job[] arr = new Job[n];
        int cost;
        String st, ed;
        int total = 0;
        for (int i = 0; i < n; i++) {
            st = sc.next();
            ed = sc.next();
            if (st.length() < 4) {
                while (st.length() != 4) {
                    st += "0";
                }
            }
            if (ed.length() < 4) {
                while (ed.length() != 4) {
                    ed += "0";
                }
            }
            cost = sc.nextInt();
            arr[i] = new Job();
            arr[i].st = getTime(st);
            arr[i].ed = getTime(ed);
            arr[i].cost = cost;
            total += cost;
        }
        Arrays.sort(arr, new SortingJobs());
        Pair res = new Pair();
        res = solve(arr, n);
        if (res == null) {
            System.out.println(0);
        } else {
            System.out.println(n - res.first);
            System.out.println(total - res.second);
        }

    }
    private static Pair solve(Job[] arr, int n) {
        if (n == 0) {
            return null;
        }
        int dp[] = new int[n];
        int numOfJobs[] = new int[n];
        for (int i = 0; i < n; i++) {
            dp[i] = 0;
            numOfJobs[i] = 0;
        }
        dp[0] = arr[0].cost;
        numOfJobs[0] = 1;
        for (int i = 1; i < n; i++) {
            int curr = arr[i].cost;
            int num = 1;
            int idx = searchJob(arr, 0, i - 1, arr[i].st);
            if (idx != curr && idx != -1) {
                curr += dp[idx];
                num += numOfJobs[idx];
            }
            if (curr > dp[i - 1]) {
                dp[i] = curr;
                numOfJobs[i] = num;
            } else {
                dp[i] = dp[i - 1];
                numOfJobs[i] = numOfJobs[i - 1];
            }
        }
        return new Pair(numOfJobs[n - 1], dp[n - 1]);
    }
    private static 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;
    }
    private static int getTime(String st) {
        int hr = (st.charAt(0) - '0') * 10 + (st.charAt(1) - '0');
        int min = (st.charAt(2) - '0') * 10 + (st.charAt(3) - '0');
        return hr * 60 + min;
    }
}