Split Clicks Into Sessions

A website logs every click as a (user, time) pair, where time is a string 'HH:MM:SS' (two digits each, hours 00 to 23) on a single day. The clicks are collected from several servers, so the list is not in time order.

A user's visit, called a session, ends when they go quiet: if more than 30 minutes (1,800 seconds) pass between two of a user's clicks in time order, the later click starts a new session. A gap of exactly 30 minutes keeps the session going.

Write sessions(clicks) that returns a list of (user, start, end, count) tuples, one per session: the user, the times of the session's first and last clicks (as 'HH:MM:SS' strings), and how many clicks it holds. Sort the list by user, then by start time.

Examples

clicks = [
    ('ana', '09:00:00'), ('ben', '09:10:00'), ('ana', '09:20:00'),
    ('ana', '10:20:01'), ('ben', '09:40:00'), ('ana', '09:50:00'),
]
sessions(clicks)
# returns [('ana', '09:00:00', '09:50:00', 3),
#          ('ana', '10:20:01', '10:20:01', 1),
#          ('ben', '09:10:00', '09:40:00', 2)]

Ana's click at 09:50:00 comes exactly 30 minutes after the one at 09:20:00, so it stays in her first session. Her next click comes 30 minutes and 1 second later and starts a new one.

Constraints

• 0 <= len(clicks) <= 100000
• User names are lower case. A user can click twice in the same second, and both clicks count.