Untitled

import java.util.*;

class PhoneCall {
    int start, end, volume;

    // Constructor to create a PhoneCall object
    public PhoneCall(int start, int duration, int volume) {
        this.start = start;
        this.end = start + duration; // Calculate end time based on start and duration
        this.volume = volume;
    }
}

public class PhoneCalls {

    public static int phoneCalls(List<Integer> start, List<Integer> duration, List<Integer> volume) {
        int n = start.size();
        PhoneCall[] calls = new PhoneCall[n];

        // Step 1: Create PhoneCall objects with start, end, and volume
        for (int i = 0; i < n; i++) {
            calls[i] = new PhoneCall(start.get(i), duration.get(i), volume.get(i));
        }

        // Step 2: Sort calls by end time (greedy approach)
        Arrays.sort(calls, (a, b) -> a.end - b.end);

        // Step 3: Use dynamic programming to maximize the volume of orders
        int[] dp = new int[n];
        dp[0] = calls[0].volume;

        for (int i = 1; i < n; i++) {
            // Include the current call's volume
            int include = calls[i].volume;
            int lastNonOverlap = findLastNonOverlapping(calls, i);

            // Add the maximum volume from the last non-overlapping call
            if (lastNonOverlap != -1) {
                include += dp[lastNonOverlap];
            }

            // The dp value is the maximum of including or excluding the current call
            dp[i] = Math.max(dp[i - 1], include);
        }

        return dp[n - 1]; // The maximum volume is stored at dp[n-1]
    }

    // Helper function to find the last non-overlapping call using binary search
    private static int findLastNonOverlapping(PhoneCall[] calls, int index) {
        int low = 0, high = index - 1;

        // Binary search to find the last call that doesn't overlap with the current one
        while (low <= high) {
            int mid = (low + high) / 2;
            if (calls[mid].end <= calls[index].start) {
                if (calls[mid + 1].end <= calls[index].start) {
                    low = mid + 1;
                } else {
                    return mid;
                }
            } else {
                high = mid - 1;
            }
        }

        return -1; // No non-overlapping call found
    }

    public static void main(String[] args) {
        // Example input as List<Integer>
        List<Integer> start = Arrays.asList(10, 5, 15, 18, 30);
        List<Integer> duration = Arrays.asList(30, 12, 20, 35, 35);
        List<Integer> volume = Arrays.asList(50, 51, 20, 25, 10);

        // Output the maximum volume of orders that can be received
        System.out.println(phoneCalls(start, duration, volume)); // Expected output: 76
    }
}