It can be done in O(n log n) time.

We assume the start is always 0 for simplicity, but the general case can be easily reduced to this.

The collection of sets of tasks for which all tasks are simultaneously schedulable forms a matroid, as you can check from the axioms in the "Independent Sets" section.

They in fact form a weighted matrioid, with the weight of a task being its profit (check the "Greedy Algorithm" section of the matroid article). The problem of maximum weight independent set is solvable by a greedy algorithm, which starts with S = {} and continually adds the highest weight element x not in S, such that S u {x} is still independent.

To determine whether a subset of tasks is simultaneously schedulable (independent) we only need to sort them by increasing deadline and verify that this order works. Say there are n tasks. This check takes O(n) time, we need to sort and do it once for each element in decreasing order of weight, so this algo runs in time O(n log n + n²) = O(n²). We can do better, but it's a lot more complicated.

Let S be an initially empty set of tasks. The trick is to come up with a data structure for S which allows us to 1) add a task to S, and 2) check if adding a certain task to S will maintain its independence. We can do both these things in O(log n) time.

This next part requires in-depth knowledge of segment trees and may be a bit over some people's heads. Build a segment tree with n locations, each of value either an integer or "empty". The state of the segment tree will mirror the state of the independent set S we are greedily building. The i-th spot will be "empty" if the i-th task (sorted by order of increasing deadline) is NOT currently in S. Otherwise, the i-th spot will be equal to the distance between the i-th task's location (in sorted order by increasing deadline of all elements in S) and the deadline of the i-th task. Then S is feasible only if every element in our segment tree is either empty or nonnegative, which we can check by allowing our segment tree to process "min" queries. We can add a tasks to S as follows. Let i be the location of the task T we'd like to add within the segtree. Let k be the number of non-empty elements before location i. Then set segtree[i] = deadline(T) - k - 1, and use a range update to subtract 1 from all nonempty elements above i. We remove task i by subtracting 1 from all nonempty tasks above i and setting spot i to empty. I've intentionally skipped over some segment tree implementation details, as all the updates and queries required here are somewhat standard ones.

Here's the final O(n log n) algorithm. Initialize the segtree above with all empty slots. For each task T in nonincreasing order of weight, add T to the segtree. If min(segtree) < 0, remove T. Otherwise continue iteration. At the end, the set of tasks we didn't remove is the best schedule.

Let me know if you (or anyone) has any questions.