Clustering/ Classifying users based on sequence of action and time

I have some user data where each user has a certain pattern of being at different places for some time. I would like to create a model which will cluster/classify these users based on these patterns and the time spent at each place. So suppose user patterns are like:

Place_1(60 min)- Place_2(30 min)- Place_5(45 min)- user 1 -label(1)

Place_1(60 min)- Place_2(60 min)- Place_5(45 min)- user 2 -label(2)

Place_1(60 min)- Place_2(60 min)- Place_5(40 min)- user 3 -label(2)

Place_2(60 min)- Place_1(60 min)- Place_5(45 min)- user 4 -label(3)

Place_2(60 min)- Place_1(60 min)- Place_5(45 min)- user 5 -label(3)

They should be clustered/classified as:

1- User 1

2- User 2, User 3

3- User 4, User 5

The time duration is continuous. Also, I already have labels for these patterns so I can do classification as well as clustering. I initially thought of doing kmeans clustering on these patterns, but introducing the duration of stay at each place is messing the clustering up. I am currently using a random forest classifier, but the results are not as promising. Any help would be highly appreciated.